题目链接【http://poj.org/problem?id=2411】
题意：给出一个h*w的矩形1<=h,w<=11.用1*2和2*1的小矩形去填满这个h*w的矩形，问有多少种方案数？
题解：用0、1表示矩形中每个位置的状态，0表示没有被铺上木块，1表示已经被铺上木块，把每一行的状态看成是一个二进制数，用十进制表示。
每一行的总状态为[0,(1<<w)-1];dp[i][j]表示第i行，状态为j,并且i行以上都被填满了的总方案数。
因为r行的状态只和r-1排的状态有关，可以用滚动数组实现。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = << ;
LL dp[][maxn];
int n, m;
int cur;
void DFS(int pos, int nu, int z)
{
if(pos == m)//处理第m个位置的时候本行已经处理完了
{
dp[cur][nu] += dp[cur ^ ][z];
return ;
}
if(!(z & ( << pos)))//如果上一行的pos位置是0,那么本行的pos位置必须是竖着放
DFS(pos + , nu | ( << pos), z);
else
{
if(pos && (!(nu & ( << pos - ))))//判断是否可以横着放
DFS(pos + , nu | ( << pos) | ( << pos - ), z);
DFS(pos + , nu, z);//不放木块，留着下一排去解决。
}
}
int main ()
{
while(~scanf("%d%d", &n, &m))
{
if(n == && m == )
break;
cur = ;
int mask = ( << m) - ;//可能的状态总数
memset(dp, , sizeof(dp));
dp[][mask] = ;//第一排的有效状态是mask
for(int i = ; i <= n; i++)
{
cur ^= ;
memset(dp[cur], , sizeof(dp[cur]));
for(int j = ; j <= mask; j++)
if(dp[cur ^ ][j])
DFS(, , j);
}
printf("%lld\n", dp[cur][mask]);
}
return ;
}