题意：给出一个n行m列的草地，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。
分析：假如我们知道第 i-1 行的所有的可以放的情况，那么对于第 i 行的可以放的一种情况，我们只要判断它和 i - 1 行的所有情况的能不能满足题目的所有牛不相邻，如果有种中满足，那么对于 i 行的这一中情况有 x 中放法。 但是我们又发现，状态是一种放法，不是我们平常dp的简单的状态，所以要用状态压缩！
dp[i][j]表示第i行状态为j的个数。
dp[i][j] = sum{dp[i-1][k]};
第i行可以由上一行的合法的状态推导来。
#include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 1000000007 #define mod 100000000 #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 13; int n,m; int mp[MAXN]; int dp[MAXN][(1<<MAXN)]; int q[1<<MAXN],cnt; int main() { while(~scanf("%d%d",&n,&m)){ int x; cnt = 0; memset(mp,0,sizeof(mp)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d",&x); if(x == 0){ mp[i] |= (1<<(j-1));//mp[i]存合法的状态 x=1的时候，用0存，0的时候用1存。 } } } memset(dp,0,sizeof(dp));//dp表示第i行状态为j时合法的个数 for(int i = 0; i < (1 << m); i++){//在一行中把没有相邻的合法的状态记录下来 if(!(i & (i << 1))){ q[cnt++] = i; } } for(int i = 0; i < cnt; i++){//对第一行初始化。由于mp存第i行合法的状态，又0用1 1用0表示，所以mp[1]&q[i]==0 //表示和合法的状态 if(!(mp[1] & q[i])){ dp[1][i] = 1; } } for(int i = 2; i <= n; i++){//从第2行开始枚举 for(int j = 0; j < cnt; j++){//枚举状态 if(mp[i] & q[j]){//不合法的状态 continue; } for(int k = 0; k < cnt; k++){ if((mp[i-1] & q[k]) == 0 && (q[j] & q [k]) == 0){ dp[i][j] = (dp[i][j] + dp[i-1][k])%mod; } } } } ll ans = 0; for(int i = 0; i < cnt; i++){ ans =(ans + dp[n][i]) % mod; } cout<<ans<<endl; } return 0; }