Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Banner

Category: JOI Tag: dp

Banner

問題概要


H*Wの平面の格子点を考える.
各点には色があり, 全部で3色ある.
ある4頂点を選んで格子の線上を辺とする長方形をつくるとき, 4頂点で全ての色を含むものはいくつあるか.

解法


まず行を2つ固定する.
そのあと列を順に見ていき, 縦方向の色の組の数を数える.
長方形はそれらのうち2個の組を組み合わせることでできるので, 全ての色をカバーできる数をそこから計算する.
これを各行の組でやればよい

コード


(banner.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

long long h, w, col[512][512], cnt[8], ans[8];

long long solve()
{
        for (int i = 0; i < h; i++) {
                for (int ii = i+1; ii < h; ii++) {
                        memset(cnt,0,sizeof(cnt));
                        for (int j = 0; j < w; j++) cnt[col[i][j]|col[ii][j]]++;
                        for (int j = 0; j < 8; j++)
                                for (int k = 0; k < 8; k++)
                                        ans[j|k] += cnt[j]*cnt[k];
                }
        }

        return ans[7]/2;
}

void input()
{
        cin >> h >> w;
        int c;
        for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++) {
                        cin >> c;
                        col[i][j] = 1<<c;
                }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments