P1879 [USACO06NOV]Corn Fields G
https://www.luogu.com.cn/problem/P1879
首先这道题，一般的区间DP状态不太好设计，很难确定父子关系。
这道题有很鲜明的特征：
1.01矩阵
2.1 ≤ M ≤ 12; 1 ≤ N ≤ 12
所以这就使人很容易想到状压DP。
下面详细说说：
f[i][j]表示前[i]行的状态为j时的合法方案数
mp[i]刻画的是土地
possi[i]判断是否合法
步骤：
1.读进来土地，把它二进制转十进制
2.判断草地是否相邻，即是否有连续的1。（i与他的左移一位和右移一位，分别做&运算，如果都都等于0，那么合法）举个例子：
比如说 6→110 （有连续的两个1，是个不合法的）
1 1 0 1 1 0
& 0 1 1 1 0 1
得：0 1 0（×） 1 0 0（×）
3.再枚举每行可能状态，判断是否有种在贫瘠土地上的情况。什么叫种在贫瘠土地上呢？就是原本土地(i,j)这个格子上是个0，你却冒出来个1，就是不行的。这有两种判断合法的方式:(j&mp[i])==j和(j|mp[i])==mp[i]。仍然举个例子：
j 0 1 0 0 1 0
mp 0 0 1 0 0 1
&得 0 0 0 （×） |得： 0 1 1（×）
AC Code：
#include <bits/stdc++.h>
using namespace std;
const int mo=1e8;
int n,m,maxn,mp[13],f[13][9000],ans;
bool possi[9000];int main()
{int x;cin>>m>>n;maxn=1<<n;f[0][0]=1;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){cin>>x;mp[i]=(mp[i]<<1)+x;//二进制转十进制 }for(int i=0;i<maxn;i++)if(!(i&(i<<1))&&!(i&(i>>1)))//判断草地是否相邻 possi[i]=true;for(int i=1;i<=m;i++)//枚举每行 for(int j=0;j<maxn;j++)//可能的状态，从00..0.~111..1 {if(possi[j]&&(j&mp[i])==j)//如果状态合法(没有相邻的1)且没有种在贫瘠的土地上 for(int k=0;k<maxn;k++)//找上一行的合法情况 if(!(k&j))//与该行状态取&不为真(0)//说明上一行与这一行不存在任意一块草地有公共边f[i][j]=(f[i][j]+f[i-1][k])%mo;//记录 }for(int i=0;i<maxn;i++)ans=(ans+f[m][i])%mo;cout<<ans<<endl;return 0;
}