没错,这道题又是我从LZL里的博客里剽过来的，他的题真不错，真香。
题目链接：http://poj.org/problem?id=2411
题目大意：给一个n * m的矩形, 要求用 1 * 2的小方块去填充满这个矩形, 有多少种填充方式。(1<=n, m <= 11)
思路：
1.凭借做题的经验，能想到这道题一定是无法用暴力去解决，因为方法数肯定很多，暴力跑不出来。
2.看到这题我想到的是用状态转移，因为大的矩形填充可以由多个小的矩形填充来组成，这是最开始的想法，但是这种想法远远不够。
3.用到状压dp，这篇博客讲解的非常清楚：https://blog.csdn.net/u014634338/article/details/50015825
4.总的来说就是先预处理出第一行的所有状态，然后dp从第2行开始，check()本行与前一行的状态是否兼容，然后把相应状态的方法数叠加上来。
5.0代表竖放,竖放的第二个砖块为1. 1代表横放,所占的两个位置都为1
代码里写了很详细的注释：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define mem(a, b) memset(a, b, sizeof(a)) 5 using namespace std; 6 7 int row, col; 8 long long dp[13][1 << 12]; //代表前 i 行,第i行状态为j时的方案数目.因此答案所求的是 dp[row][(1 << m) - 1] 9 10 int ok(int state) 11 { 12 for(int j = 0; j < col; ) //枚举每一列的状态 前j列已经被确定 13 { 14 if(state & (1 << j)) //第 j 列为 1 15 { 16 if(j == col - 1) //列数不够 17 return 0; 18 if(state & (1 << (j + 1))) //第 j + 1列为 1, 横放 19 j += 2; 20 else//第 j + 1 列为 0, 在第 j 列还未被确定的情况下是不合法的 21 return 0; 22 } 23 else//第 j 列为 0, 竖放 24 { 25 j += 1; 26 } 27 } 28 return 1; 29 } 30 31 int check(int now, int pre) 32 { 33 for(int j = 0; j < col; )//枚举每一列判断是否与前一行有冲突 34 { 35 if(now & (1 << j))//第i行第j列为1 36 { 37 if(pre & (1 << j))//第i-1行第j列也为1，那么第i行必然是横放 38 { 39 if(j == col - 1) 40 return 0; 41 if(!(now & (1 << (j + 1))) || !(pre & (1 << (j + 1)))) 42 //第i行和第i-1行的第j+1都必须是1，否则是非法的 43 return 0; 44 j += 2; 45 } 46 else //第i-1行第j列为0，说明第i行第j列是竖放 47 j += 1; 48 } 49 else //第i行第j列为0，那么第i-1行的第j列应该是已经填充了的 50 { 51 if(pre & (1 << j)) 52 j += 1; 53 else 54 return 0; 55 } 56 } 57 return 1; 58 } 59 60 int main() 61 { 62 while(scanf("%d%d", &row, &col) != EOF) 63 { 64 if(row == 0 && col == 0) 65 break; 66 if(col > row) //将图较小边作为宽，这样一行中的状态数较少，可以提高效率 67 swap(col, row); 68 if((row * col) % 2) //若面积为 奇数 , 则不可能存在覆盖满的情况 69 { 70 printf("0 "); 71 continue; 72 } 73 mem(dp, 0); 74 int tot = 1 << col; 75 for(int i = 0; i < tot; i ++) //枚举第1行的所有状态,初始化第1行的方案数 76 { 77 if(ok(i)) 78 dp[1][i] = 1; 79 } 80 for(int i = 2; i <= row; i ++) //dp从第2行开始,因为第1行已经预处理了 81 { 82 for(int j = 0; j < tot; j ++)//第 i 行的状态 83 { 84 for(int k = 0; k < tot; k ++)//第 i - 1行的状态 85 { 86 if(check(j, k)) 87 dp[i][j] += dp[i - 1][k]; 88 } 89 } 90 } 91 printf("%lld ", dp[row][(1 << col) - 1]); 92 } 93 return 0; 94 }