POJ 2411 Mondriaan's Dream/[二进制状压DP]

题目链接【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 = 1 << 12;
LL dp[2][maxn];
int n, m;
int cur;
void DFS(int pos, int nu, int z)
{
    if(pos == m)//处理第m个位置的时候本行已经处理完了
    {
        dp[cur][nu] += dp[cur ^ 1][z];
        return ;
    }
    if(!(z & (1 << pos)))//如果上一行的pos位置是0,那么本行的pos位置必须是竖着放
        DFS(pos + 1, nu | (1 << pos), z);
    else
    {
        if(pos && (!(nu & (1 << pos - 1))))//判断是否可以横着放
            DFS(pos + 1, nu | (1 << pos) | (1 << pos - 1), z);
        DFS(pos + 1, nu, z);//不放木块，留着下一排去解决。
    }
}
int main ()
{
    while(~scanf("%d%d", &n, &m))
    {
        if(n == 0 && m == 0)
            break;
        cur = 0;
        int mask = (1 << m) - 1;//可能的状态总数
        memset(dp, 0, sizeof(dp));
        dp[0][mask] = 1;//第一排的有效状态是mask
        for(int i = 1; i <= n; i++)
        {
            cur ^= 1;
            memset(dp[cur], 0, sizeof(dp[cur]));
            for(int j = 0; j <= mask; j++)
                if(dp[cur ^ 1][j])
                    DFS(0, 0, j);
        }
        printf("%lld
", dp[cur][mask]);
    }
    return 0;
}