POJ 3254 Corn Fields（状态压缩DP）

题目大意：给出一个M*N的矩阵，元素为0表示这个地方不能种玉米，为1表示这个地方能种玉米，现在规定所种的玉米不能相邻，即每行或者没列不能有相邻的玉米，问一共有多少种种植方法。

举个例子：

2 3
1 1 1
0 1 0
表示2*3的玉米地，现在一共有多少种种植方法呢？ 答案：种0个玉米（算一个合法方案）+种1个玉米（4）+种2个玉米（3）+种3个玉米（1）=9

（题意是复制的，链接：http://www.cnblogs.com/buptLizer/archive/2012/08/22/2650717.html）

题解：

这也算是我入门状压DP的第一道题了吧，看了好几天了，今天也算是差不多懂了。本题就是先把地图存下来，存到了row数组中，其中row【i】就代表了一行的地图，又初始化了一个state数组，存的也是数字，是可行状态的二进制情况，之后就是DP数组了。

dp【i】【j】：表示第i行，第j种可行的情况下有多少种情况。

所以方程是dp[i][j]=(dp[i][j]+dp[i-1][k])   0<=k<numst

AC代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <string>
#include <cassert>
#include <climits>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define prN printf("
")
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const int mod=100000000;
int n,m;
int row[15],dp[15][1<<15];
int state[1<<15],numst;
void init()
{
    int num=1<<m;
    numst=0;
    rep(i,num)
    {
        if ((i&(i<<1))==0)/**< 这有问题，(i&(i<<1))==0 这两个括号都必须加上，位运算优先级很难搞懂，所以有位运算就全家上括号 */
        {
            state[numst++]=i;
        }
    }
}

int main()
{

    SII(n,m);
    init();
    int c1;
    rep(i,n)
    {
        reRep(j,m-1,0)
        {
            SI(c1);
            row[i]|=c1<<j;
        }
    }

    rep(i,numst)//dp的初始状态，要赋为1或0
    {
        dp[0][i]=((row[0]&state[i])==state[i])?1:0;
    }

    /**< i是这一行，j是这一个，k是上一行可行的其中一个 */
    Rep(i,1,n-1)
    {
        rep(j,numst)
        {
            if ((row[i]&state[j])!=state[j])
                continue;
            rep(k,numst)
            {
                if (dp[i-1][k]&&(state[k]&state[j])==0)/**< 又是这位运算的问题，再说一遍，位运算，一定要走一步加一次括号！！！ */
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
            }
        }
    }


    int res=0;
    rep(i,numst)
    {
        res=(dp[n-1][i]+res)%mod;
    }
    printf("%d
",res);

    return 0;
}