Poj2411 Mondriaan's Dream
题意:给出一个n*m的矩形，然后用1*2大小的多米若骨牌去填充n*m的这个矩形，问有多少种填充方法。
一个可行的解法就是轮廓线dp。 假设我们从上往下，从左往右去填，那么我们会发现，假如我们当前填的是(i,j)格的时候，在它前面的(i',j')其实
是已经确定一定填了的，所以实际上没有填的时候处于轮廓线的部分，
1 1 1 1 1 1 x x x x
当放置(i,j)时，（i',j'）(在i，j之前的其实已经防止好了)于是只需考虑(i，j)的三种情况，不放，横放，竖着放。
采用状态压缩，和滚动数组。
dp公式。
for j=1-m;
dp[cur][k]+=dp[1-cur][j];
列举集合的一些运用：
只含有第i个元素的集合：1<<i
含有从0开始的n个元素的集合: 1<<n-1
判断第i个元素是否属于集合S：if(S>>i&1)
向集合中加入第i个元素：S|(1<<i)
向集合中删去第i个元素：S&~(1<<i)
判断集合T是否为S的子集:if((S|T)==S)
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int n,m,cur; const int maxn=15; long long d[2][1<<maxn]; //滚动数组 void update(int a,int b) { if(b&(1<<m)) { d[cur][b^(1<<m)]+=d[1-cur][a]; } } int main() { while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; if(n<m) swap(n,m); memset(d,0,sizeof(d)); cur=0; d[0][(1<<m)-1]=1; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cur^=1; memset(d[cur],0,sizeof(d[cur])); //滚动数组的特点，必须在这里才能置为零。 for(int k=0;k<(1<<m);k++) { update(k,k<<1); //不放 if(i&&!(k&(1<<m-1))) update(k,(k<<1)^(1<<m)^1); //竖着放 if(j&&!(k&1)) update(k,(k<<1)^3);//横着放 } } } printf("%lld\n",d[cur][(1<<m)-1]); } return 0; }
