没错,这道题又是我从LZL里的博客里剽过来的，他的题真不错，真香。
题目链接：http://poj.org/problem?id=2411
题目大意：给一个n * m的矩形, 要求用 1 * 2的小方块去填充满这个矩形, 有多少种填充方式。(1<=n, m <= 11)
思路：
1.凭借做题的经验，能想到这道题一定是无法用暴力去解决，因为方法数肯定很多，暴力跑不出来。
2.看到这题我想到的是用状态转移，因为大的矩形填充可以由多个小的矩形填充来组成，这是最开始的想法，但是这种想法远远不够。
3.用到状压dp，这篇博客讲解的非常清楚：https://blog.****.net/u014634338/article/details/50015825
4.总的来说就是先预处理出第一行的所有状态，然后dp从第2行开始，check()本行与前一行的状态是否兼容，然后把相应状态的方法数叠加上来。
5.0代表竖放,竖放的第二个砖块为1. 1代表横放,所占的两个位置都为1
代码里写了很详细的注释：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std; int row, col;
long long dp[][ << ]; //代表前 i 行,第i行状态为j时的方案数目.因此答案所求的是 dp[row][(1 << m) - 1] int ok(int state)
{
for(int j = ; j < col; ) //枚举每一列的状态 前j列已经被确定
{
if(state & ( << j)) //第 j 列为 1
{
if(j == col - ) //列数不够
return ;
if(state & ( << (j + ))) //第 j + 1列为 1, 横放
j += ;
else//第 j + 1 列为 0, 在第 j 列还未被确定的情况下是不合法的
return ;
}
else//第 j 列为 0, 竖放
{
j += ;
}
}
return ;
} int check(int now, int pre)
{
for(int j = ; j < col; )//枚举每一列判断是否与前一行有冲突
{
if(now & ( << j))//第i行第j列为1
{
if(pre & ( << j))//第i-1行第j列也为1，那么第i行必然是横放
{
if(j == col - )
return ;
if(!(now & ( << (j + ))) || !(pre & ( << (j + ))))
//第i行和第i-1行的第j+1都必须是1，否则是非法的
return ;
j += ;
}
else //第i-1行第j列为0，说明第i行第j列是竖放
j += ;
}
else //第i行第j列为0，那么第i-1行的第j列应该是已经填充了的
{
if(pre & ( << j))
j += ;
else
return ;
}
}
return ;
} int main()
{
while(scanf("%d%d", &row, &col) != EOF)
{
if(row == && col == )
break;
if(col > row) //将图较小边作为宽，这样一行中的状态数较少，可以提高效率
swap(col, row);
if((row * col) % ) //若面积为 奇数 , 则不可能存在覆盖满的情况
{
printf("0\n");
continue;
}
mem(dp, );
int tot = << col;
for(int i = ; i < tot; i ++) //枚举第1行的所有状态,初始化第1行的方案数
{
if(ok(i))
dp[][i] = ;
}
for(int i = ; i <= row; i ++) //dp从第2行开始,因为第1行已经预处理了
{
for(int j = ; j < tot; j ++)//第 i 行的状态
{
for(int k = ; k < tot; k ++)//第 i - 1行的状态
{
if(check(j, k))
dp[i][j] += dp[i - ][k];
}
}
}
printf("%lld\n", dp[row][( << col) - ]);
}
return ;
}