poj 3254(状圧dp入門)

タイトルリンク: http://poj.org/problem?id=3254
状圧dpは一般的に範囲が小さく、このようなdpの一般的なデータ範囲は小さい(16を超えないようだが)、このようなデータ範囲を見ると状圧に考えることができる.
まず下位演算を行い、      '&'   2つの数のバイナリを操作することを表し、同じビットがすべて1の場合、このビットの最終結果は1になります.
                                y>>xは、数yのバイナリを右にxビットシフトし、低位を捨てることを表し、高位は0を補う
                                 <<     えんざんしどうり
 
标题:農夫FJにはn行m列の矩形の土地があり、ある土地は肥沃で、これらの土地で牛を放すことができ(1で表す)、ある土地で牛を放すことができない(0で表す)、しかも隣接する牛を放すことができる格子は同時に牛を放すことができない.
分析:サンプルを例にとると、私たちは1行1行考えることができます.行ごとに1で牛を放す、0で牛を放さない、
1行目の状態は、1000001010011(破棄)100101110(破棄)111(破棄)
題意に合った状態は5つしかないので、最初の行には5つの案があります.
2行目のステータス:000010
しかし、2行目の010と1行目の010が衝突するため、2行目の状態が010の場合、4つのスキームがある.ステータスが000の場合、5つのシナリオがあるので、全部で4+5=9のシナリオがあります.
分析が終わると、各行に対して01列でこの行の状態を表すことができ、この状態は10進数整数で代用することができ、つまり、この状態を10進数整数に圧縮したので、状態圧縮と呼ぶことができる.
本題では,dp[i][j]はi行目の状態がjの場合のシナリオ数を表す.
状態圧縮dpで最も一般的なのはビット演算であり、ビット演算は現在の状態が合法かどうかを容易に判断できるからである.例えば本題ではi行目に隣接する2つの土地が同時に牛がいるか否かを判断し,現在の状態がXであると仮定すると,X&(X>>1)またはX&(X<<1)の結果が0であるか否かを判断するだけで,0であれば隣接していないことを説明し,そうでなければ隣接していることを説明する.
ACコード:

#include
#include
#include
using namespace std;
 
const int mod = 100000000;
const int maxn = 1 << 12 + 4;    // +     MLE
int dp[14][maxn];   //  i ,j         
vectorv[14];   //   i    
int mp[14][14];      //    
int n , m;
 
//   x  mp[x][j]   ,        ( 0 1,1 0)        ,                  
int state(int x){    
    int s = 0;
    int tmp = 1;
    for(int i = m;i >= 1;-- i){
        s += (!mp[x][i]) * tmp;
        tmp *= 2;
    }
    return s;
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        memset(dp,0,sizeof(dp));
        memset(v,0,sizeof(v));
        memset(mp,0,sizeof(mp));
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++)
                scanf("%d",&mp[i][j]);
        }
        v[0].push_back(0);                          //                
        int k = 1 << m;                             //     m,                2 m   - 1 ,  k - 1;
        for(int i = 0;i < k;i ++)
            dp[0][i] = 1;                           //               ,       
        for(int i = 1;i <= n;i ++){
            int tmp = state(i);
            for(int j = 0;j < k;j ++){
                if(j & (j << 1)) continue;         //  j           1
                if(j & tmp) continue;              //  tmp    mp          (   1  ,   ,    )
                v[i].push_back(j);                 //          v[i]
            }
            for(int j = 0;j < v[i].size();j ++){
                int now = v[i][j];                   // v[i]            
                for(int f = 0;f < v[i-1].size();f ++){
                    int last = v[i-1][f];            // v[i-1]           
                    if(now & last) continue;        //  (     )
                    dp[i][now] = (dp[i][now] + dp[i-1][last]) % mod;
                }
            }
        }
        int ans = 0;
        for(int i = 0;i < k;i ++)
            ans = (ans + dp[n][i]) % mod;
        printf("%d
",ans);
    }
    return 0;
}