1、poj 3254 Corn Fields 状态压缩dp入门题
2、总结：二进制实在巧妙，以前从来没想过可以这样用。
题意：n行m列，1表示肥沃，0表示贫瘠，把牛放在肥沃处，要求所有牛不能相邻，求有多少种放法。
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#define max(a,b) a>b?a:b
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const int mod=;
const int N=<<; int m,n,num;
int mapn[],line[N]; //mapn存储每行状态，line枚举出所有每行本身不相邻的状态
int dp[][N]; int is1(int i) //判断i本身二进制是否相邻
{
return (i&(i>>));
} int is2(int i,int j) //判断i与j二进制是否相邻
{
return (mapn[i]&line[j]);
} void solve()
{
memset(dp,,sizeof(dp));
for(int i=;i<num;i++){
if(!(is2(,i)))dp[][i]=;
} for(int i=;i<=m;i++){
for(int j=;j<num;j++){ //枚举第i行可能的情况
if(is2(i,j))continue; //剪枝
for(int l=;l<num;l++){ //枚举i-1行可能的情况
if(dp[i-][l]&&(!(line[j]&line[l]))){
dp[i][j]+=dp[i-][l];
}
}
}
} int sum=;
for(int i=;i<num;i++){
sum+=dp[m][i];
sum%=mod;
}
printf("%d\n",sum);
} int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(mapn,,sizeof(mapn));
int a;
for(int i=;i<=m;i++){
for(int j=;j<n;j++){
scanf("%d",&a);
if(!a){
mapn[i]+=(<<j); //存储下每行的状态，取a为0时才可比较
}
}
} memset(line,,sizeof(line));
num=;
for(int i=;i<(<<n);i++){
if(!is1(i))line[num++]=i; //存储下所有本身二进制不相邻的数
} solve();
} return ;
}