POJ 2411 Mondriaan'sDream

 1 /*
 2     题意：一个h*w的矩阵（1<=h,w<=11），只能放1*2的模块，问完全覆盖的不同放发有多少种？
 3     状态压缩DP第一道：dp[i][j] 代表第i行的j状态下的种数(状态即为二进制10101110101...的样子)
 4                         横着的定义为11，竖着的定义为01，当两行的状态已填满并且没有出现奇数个1时，累加个数
 5                             即两行状态相或要全为1，两行相与要没有连续的1的个数是奇数个
 6 */
 7 #include <cstdio>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <cmath>
11 #include <cstring>
12 #include <map>
13 using namespace std;
14 
15 const int MAXN = 1e4 + 10;
16 const int INF = 0x3f3f3f3f;
17 long long dp[20][3010];
18 
19 bool ok(int x)
20 {
21     int res = 0;
22     while (x)
23     {
24         if (x & 1)  res++;
25         else
26         {
27             if (res & 1)    return false;
28             res = 0;
29         }
30 
31         x >>= 1;
32     }
33     if (res & 1)    return false;
34     else    return true;
35 }
36 
37 int main(void)      //POJ 2411 Mondriaan‘sDream
38 {
39     #ifndef ONLINE_JUDGE
40     freopen ("A.in", "r", stdin);
41     #endif
42 
43     int n, m;
44     while (~scanf ("%d%d", &n, &m) && n && m)
45     {
46         memset (dp, 0, sizeof (dp));
47         int tot = (1 << m);
48         for (int i=0; i<tot; ++i)
49         {
50             if (ok (i)) dp[1][i] = 1;
51         }
52 
53         for (int i=1; i<=n-1; ++i)
54         {
55             for (int j=0; j<tot; ++j)
56             {
57                 if (dp[i][j])
58                 {
59                     for (int k=0; k<tot; ++k)
60                     {
61                         if ((j | k) == tot - 1 && ok (j & k))
62                         {
63                             dp[i+1][k] += dp[i][j];
64                         }
65                     }
66                 }
67             }
68         }
69 
70         printf ("%I64d\n", dp[n][tot-1]);
71     }
72 
73     return 0;
74 }