状压dp的一种经典模型,覆盖问题。
我们定义f[i][j]表示当第i行的状态为j时,前i行的方案数。显然答案为f[n][0].
关于压缩状态,我们定义一个m位的二进制数,其中第i位为1的含义是,第i列是一个竖着的矩形的上半部分。第i位为0则表示其他情况。
因此,第i-1行的状态k能转移到第i行的状态j,当且仅当:
- k&j的值为0.这保证了每一个1下面都是0。代表继续补全这个矩形。
- j|k的结果的二进制表示中,每一段连续的0都必须有偶数个。因为这些0表示横躺着的矩形,当为奇数时不符合题意。(我们预处理符合题意的情况记录在集合S中)
写成公式就是
因此,我们可以在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 ",f[n][0]); 23 } 24 return 0; 25 }