合法布阵问题
P1879 [USACO06NOV]玉米田Corn Fields
题意：给出一个n行m列的草地(n,m<=12)，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。
分析：假如我们知道每行都有x种合法放法（也就是x种状态），所以对于第i行就有x种放法，那么对于第i+1行的每种放法就有对应的x种放法。
所以定义dp[i][j]表示第i行状态为j时的方法数(j=0,j<=x;j++)，有转移方程：dp[i][j]=sum(dp[i-1][k]) k表示i-1行的状态(k=0,k<=x;k++)。
然而，动归方程想出来了还远远不够……/*orz_wa*/
1、预处理第i行的草地map[i]，用一个二进制数表示，1表示不能放，0表示可以放。如map[1]=15,转成二进制数就是01111，就说明是 放，不放，不放，不放，不放。二进制的神奇！！！
（常理应该是1能放 0不能放，具体原因等下就知道了，主要是方便位运算）。
2、预处理第i行符合条件（不相邻）的状态st[i]，每行共有(1<<m)-1种状态（一个点2种，二个点4种，三个点8种……）。（i=1;i<=(1<<m)-1;i++）
但是很多是相邻的，怎么判断某一状态是否相邻：i&(i<<1)
3、怎么处理肥沃贫瘠问题呢，对于第i行的地形map[i]和某一状态st[k]，如果map[i]&st[k]>=1（如map[2]=10010,st[2]=01110,那么map[2]&st[2]=00010=2>1,所以重复了，关键：同1为1，否则为0）即说明出现了放到贫瘠草地的情况
4、对于第i行不和i-1行相邻，st[i]&st[i-1]>=1，同上（3）即不满足（转换为st[i]&st[i-1]==0），st[i]是第i行的状态，st[i-1]是i-1行的状态
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int mod=;
int n,m;
int st[<<],map[<<];//分别表示每一行的状态和草地的状态
int dp[][<<];
int main()
{
scanf("%d%d",&n,&m);
int x;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&x);
if(x==)map[i]=map[i]|(<<j-);
}
int k=;
for(int i=;i<=(<<m)-;i++)//计算每行合法的放置方式
{
if(!(i&(i<<)))st[++k]=i;
}
for(int i=;i<=k;i++)//特判第一行
{
if(!(st[i]&map[]))dp[][i]=;
}
for(int i=;i<=n;i++) //列举每一行（除了第一行）
{
for(int j=;j<=k;j++) //每行可能情况
{
if(!(map[i]&st[j])) //符合土地肥沃贫瘠
for(int r=;r<=k;r++) //i-1行的情况
{
if(!(map[i-]&st[r])) // i-1行r状态符合土地肥沃贫瘠
{
if(!(st[j]&st[r])) // i行j状态和i-1行r状态是否相邻
dp[i][j]+=dp[i-][r]; //加方案数量
}
}
}
}
int ans=;
for(int i=;i<=k;i++) {
ans=(ans+dp[n][i])%mod; //答案？？
}
printf("%d",ans);
return ;
}
总结：确定状态，从一维转向二维……（做多了就有经验，from_Mr.Li）