http://poj.org/problem?id=3254
题面来自洛谷：https://www.luogu.org/problemnew/show/1879
农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
————————————————————————————
十分基础的状压dp，然而我的状压十分的垃圾（从NOIP开始就不会写一道状压的我……）
设f[i][j]表示i行的状态为j的方案个数。
显然我们可以把地图的二进制先保存下来，然后利用它判断状态是否合法。
根据题做多的想法，我们考虑与原图&一下，但显然是不行的——因为一棍下去会打死一批正确的。
那么我们可以对原图取反再&，这样就可以了。
接下来判断一个状态是否合法，只需要（和上题一样BZOJ1087互不侵犯）j&j<<1即可。
同样判断两个状态合法就k&j即可。
转移方程就是对所有符合的都有dp[i][k]+=dp[i-1][j]（k和j为枚举且合法的状态）
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=4096; const int p=1e8; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int g[N],n,m,mp[15]; int ans,dp[15][N]; int main(){ m=read();n=read(); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ mp[i]+=(1-read())*(1<<n-j); } } int t=1<<n; for(int i=0;i<t;i++){ if(i&mp[1]||(i&i<<1))continue; dp[1][i]=1; } for(int i=2;i<=m;i++){ for(int k=0;k<t;k++){ if((k&mp[i])||(k&k<<1))continue; for(int j=0;j<t;j++){ if(j&mp[i-1]||(j&j<<1))continue; if(k&j)continue; dp[i][k]+=dp[i-1][j]; dp[i][k]%p; } } } for(int k=0;k<t;k++)ans=(ans+dp[m][k])%p; printf("%d ",ans); return 0; }