JOI 11 Day1 Banner ( DP )

banner: 横断幕 (Banner) - 2011年 日本情報オリンピック春合宿OJ | AtCoder
問題：h ≤ 400, w ≤ 400 の長方形が与えられる。全てのマスにはそれぞれ 0 ~ 2の色のどれかが付いている。その中四つの隅で確定する長方形で、四つの隅の中に全ての色が付いてる選び方を出力する。
普通に上下を決めて、左右をDPでなんとかする。色をバイナリでエンコードすると楽。

#include <bits/stdc++.h>
using namespace std;
const int MAXH = 400 + 4;
const int MAXW = 400 + 4;
typedef long long ll;

int h, w;
int col[ MAXH ][ MAXW ];

ll dp[ 1 << 3 ]; // number of ways having color 0 / 1 / 2

void solve(){
    ll ans = 0;
    for(int i = 1; i <= h; ++i)
        for(int j = i; j <= h; ++j){
            memset( dp, 0, sizeof(dp) );
            for(int k = 1; k <= w; ++k){
                int k_col = 0;
                k_col |= 1 << ( col[ i ][ k ] );
                k_col |= 1 << ( col[ j ][ k ] );
                for(int s = 1; s < ( 1 << 3 ); ++s)
                    if( ( s | k_col ) == ( 1 << 3 ) - 1 )
                        ans += dp[ s ];
                ++dp[ k_col ];
            }
        }
    printf("%lld\n", ans);
}

int main(){
    scanf("%d%d", &h, &w);
    for(int i = 1; i <= h; ++i)
        for(int j = 1; j <= w; ++j)
            scanf("%d", &col[ i ][ j ]);
    solve();
    return 0;
}