poj 2411 Mondriaan's Dream(状态压缩dP)

题目：http://poj.org/problem?id=2411

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

题意：一个矩阵，只能放1*2的木块，问将这个矩阵完全覆盖的不同放法有多少种。

思路:一道很经典的状态dp,但是还是很难想，横着放定义为11，竖着放定义为01.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 using namespace std;
 6 __int64 d[12][1<<12], f[1<<12];//用———int64,因为有可能数很大
 7 int h, w, full;
 8 
 9 bool ok(int x) //判断一行里是否出现连续奇数个1，第一行的话不允许
10 {
11     int sum = 0;
12     while(x>0)
13     {
14         if((x&1)==1)
15         sum++;
16         else
17         {
18             if((sum&1)==1)
19             return false;
20             sum = 0;
21         }
22         x = (x>>1);
23     }
24     if((sum&1)==1)
25             return false;
26     return true;
27 }
28 bool check(int x1, int x2)
29 {
30     int xx = (1<<w)-1;
31     if((x1|x2)==xx&&f[x1&x2])//去掉竖着00和竖着单独11的情况，一定不要忘了单独11的情况
32     return true;
33     return false;
34 }
35 int main()
36 {
37     int i, j, k;
38     memset(f, 0, sizeof(f));
39     full = (1<<11);
40 
41     for(i = 0; i < full; i++)
42     if(ok(i))
43     f[i] = 1;   //记录连续的奇数个1
44     while(~scanf("%d%d", &h, &w))
45     {
46         if(h==0&&w==0)
47         break;
48         full = (1<<w);
49         memset(d, 0, sizeof(d));
50         for(i = 0; i < full; i++)
51         if(f[i])
52         d[0][i] = 1;
53 
54         for(k = 1; k < h; k++)
55         for(i = 0; i < full; i++)
56         for(j = 0; j < full; j++)
57         {
58             if(check(i, j))
59             d[k][i] += d[k-1][j];
60         }
61         printf("%I64d
", d[h-1][full-1]); //最后一行，而且满1
62     }
63     return 0;
64 }