Mondriaan's Dream
POJ题目
一道看起来超级难，但代码很短的状压DP
还是用01来刻画图，每一个11的小正方形是0，所以说横着放的12的长方形0的个数总会是2的倍数，也就是说不可能有连续的奇数个0；竖着放的1*2的长方形看做是1，比如说第1行是1，那么第二行的那个位置就是0，竖着放，上下各一半嘛。
f[i,j]表示第i行的形态为j时，前i行的方案总数，j是用十进制数记录的N位二进制数。
第i-1行的形态k能转移到第i行的形态j，只有一下两种情况：
1.j和k位与运算的结果是0
这保证每个数字1下面必须是0，代表继续补全竖着的1*2长方形
2.j和k位或运算的结果在二进制的表示中，连续的0都为偶数个。
这些0代表着若干个横着的1*2长方形，奇数个0无法分割。
#include <bits/stdc++.h>
using namespace std;int n,m;
long long f[12][1<<11];
bool ins[1<<11];int main()
{while(cin>>n>>m&&n){for(int i=0;i<1<<m;i++){bool cnt0=0,odd=0;//cnt0记录连续0的个数 for(int j=0;j<m;j++)if(i>>j&1) odd|=cnt0,cnt0=0;else cnt0^=1;ins[i]=odd|cnt0?0:1;}f[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<1<<m;j++){f[i][j]=0;for(int k=0;k<1<<m;k++)if((j&k)==0&&ins[j|k]) f[i][j]+=f[i-1][k]; }cout<<f[n][0]<<endl;}return 0;
}