[C++知识库]玉米田（状压dp）

###题目内容：
农夫约翰的土地由 M×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式
第 1 行包含两个整数 M 和 N。

第 2…M+1 行：每行包含 N 个整数 0 或 1，用来描述整个土地的状况，1 表示该块土地肥沃，0 表示该块土地不育。

输出格式
输出总种植方法对 108 取模后的值。

数据范围
1≤M,N≤12

思路:首先将玉米田反过来存储，便于用按位与运算判断，然后用b[i]存储第i行的玉米田二进制表示，接着dp得到每一行的状态，如果初始化第0行所有状态为1，那么第一行状态就不需要分开写，否则就要分开写，注意每次都要对10^8取余防止爆内存。

（1）其中j&(j<<1)是判断横向是否有玉米相邻种植
（2）j&b[i]是对当前行玉米地判断是否在不育的地方上种上了玉米
（3）还有就是要与f[i-1][t]按位与，确保上下两行不会冲突
就这三个要点判断

AC代码：

using namespace std;
int a[13][13];
int f[13][16384]; 
int b[13];
int n,m;
int t;
int ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        t=0;
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            a[i][j]=(a[i][j]^1);
            if(a[i][j]==1)
            {
                t+=(1<<(m-j));
            }
         }
         b[i]=t; //存储每行玉米田反二进制表示 
    }
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            for(int j=0;j<(1<<m);j++)
            {
                if((j&b[1])==0&&(j&(j<<1))==0)f[1][j]=1;
            }
        }
        else 
        {
            for(int j=0;j<(1<<m);j++)//上一行状态 
            {
                if(f[i-1][j]!=0)//如果上一行有该状态 
                {
                    for(int k=0;k<(1<<m);k++)
                    {
                      if((k&j)==0&&(k&(k<<1))==0&&(k&b[i])==0)
                      {
                        f[i][k]+=f[i-1][j];
                        f[i][k]%=100000000;
                          } 
                    }
                }
            }
        }
    }
    for(int i=0;i<(1<<m);i++)
    {
        ans+=f[n][i];
        ans%=100000000;
    }
    cout<<ans<<endl;
    return 0;
    /**测试数据 
    4 10
    0 1 1 1 1 1 1 1 1 1
    1 1 1 0 1 1 1 1 1 1
    1 1 1 1 1 1 0 1 1 1
    0 0 1 1 1 1 1 1 1 0
    ans:4402955
    **/
}