HDU 1400 Mondriaan's Dream [状态压缩DP]

　　题目问用1*2组成如图h*w矩形的方案有多少种。　

　　明显的状态压缩DP，从上向下填充，假设两行的状态为stat1和stat2，则需要满足的条件是stat1|sta2=1<<w-1以及stat1&stat2中连续的1都是偶数个。因为上一行为空的下一行必须放一个竖的，而除去竖着到上一行的都是横着的，每一个横着的占的宽度都是2，所以stat1&stat2中连续的1肯定是偶数个。

　　对每一层要记录一个状态是否搜过，并记录这个状态有多少种方法，即记忆化搜索。复杂度是O(h*(2^w)*(2^w))。

　　斌牛的方法更为高效简洁，状态表示的是当前轮廓线的状态，复杂度是O(h*w*(2^w))，传送门在这里，http://www.cnblogs.com/staginner/archive/2012/09/04/2670729.html 。

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <set>
 4 typedef long long LL;
 5 int h,w,full;
 6 LL d[12][2200],res[12][12];
 7 int doublei(int state){
 8     for(int i=0,d=0;i<=w;i++)
 9         if(i<w&&((state>>i)&1))d++;
10         else if(d&1)return 0;
11     return 1;
12 }
13 LL dfs(int state,int step){
14     if(d[step][state]!=-1)return d[step][state];
15     if(step==h)return state==full-1;
16     d[step][state]=0;
17     for(int i=0;i<full;i++){
18         if((i|state)!=full-1||!doublei(state&i))continue;
19         d[step][state]+=dfs(i,step+1);
20     }
21     return d[step][state];
22 }
23 int main(){
24      while(scanf("%d%d",&h,&w),h||w){
25         if(res[w][h])printf("%I64d\n",res[w][h]);
26         else{
27             full=(1<<w);
28             memset(d,-1,sizeof d);
29             printf("%I64d\n",res[w][h]=res[h][w]=dfs(full-1,0));
30         }
31     }
32     return 0;
33 }