状压dp的一种经典模型，覆盖问题。
我们定义f[i][j]表示当第i行的状态为j时，前i行的方案数。显然答案为f[n][0].
关于压缩状态，我们定义一个m位的二进制数，其中第i位为1的含义是，第i列是一个竖着的矩形的上半部分。第i位为0则表示其他情况。
因此，第i-1行的状态k能转移到第i行的状态j，当且仅当：
因此，我们可以在dp之前预处理出每一种状态是否符合条件2即可实现O(1)的转移，总时间复杂度为O(4mn).
1 #include <iostream> 2 using namespace std; 3 int n,m; 4 long long f[12][1<<12]; 5 bool ok[1<<12]; 6 int main() { 7 while(cin>>n>>m&&n+m) { 8 for(int i=0;i<1<<m;i++) { 9 bool pd=0,x=0; 10 for(int j=0;j<m;j++) 11 if(i>>j&1) pd|=x,x=0; 12 else x^=1; 13 ok[i]=x|pd?0:1; 14 } 15 f[0][0]=1; 16 for(int i=1;i<=n;i++) 17 for(int j=0;j<1<<m;j++) { 18 f[i][j]=0; 19 for(int k=0;k<1<<m;k++) 20 if(!(k&j)&&ok[j|k]) f[i][j]+=f[i-1][k]; 21 } 22 printf("%lld\n",f[n][0]); 23 } 24 return 0; 25 }
原文：https://www.cnblogs.com/shl-blog/p/10701262.html
