状压DP POJ 2411 Mondriaan'sDream

题目传送门

/*
    题意：一个h*w的矩阵（1<=h,w<=11），只能放1*2的模块，问完全覆盖的不同放发有多少种？
    状态压缩DP第一道：dp[i][j] 代表第i行的j状态下的种数(状态即为二进制10101110101...的样子)
                        横着的定义为11，竖着的定义为01，当两行的状态已填满并且没有出现奇数个1时，累加个数
                            即两行状态相或要全为1，两行相与要没有连续的1的个数是奇数个
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;

const int MAXN = 1e4 + 10;
const int INF = 0x3f3f3f3f;
long long dp[20][3010];

bool ok(int x)
{
    int res = 0;
    while (x)
    {
        if (x & 1)  res++;
        else
        {
            if (res & 1)    return false;
            res = 0;
        }

        x >>= 1;
    }
    if (res & 1)    return false;
    else    return true;
}

int main(void)      //POJ 2411 Mondriaan'sDream
{
    #ifndef ONLINE_JUDGE
    freopen ("A.in", "r", stdin);
    #endif

    int n, m;
    while (~scanf ("%d%d", &n, &m) && n && m)
    {
        memset (dp, 0, sizeof (dp));
        int tot = (1 << m);
        for (int i=0; i<tot; ++i)
        {
            if (ok (i)) dp[1][i] = 1;
        }

        for (int i=1; i<=n-1; ++i)
        {
            for (int j=0; j<tot; ++j)
            {
                if (dp[i][j])
                {
                    for (int k=0; k<tot; ++k)
                    {
                        if ((j | k) == tot - 1 && ok (j & k))
                        {
                            dp[i+1][k] += dp[i][j];
                        }
                    }
                }
            }
        }

        printf ("%I64d
", dp[n][tot-1]);
    }

    return 0;
}