状压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 + ;
const int INF = 0x3f3f3f3f;
long long dp[][]; bool ok(int x)
{
int res = ;
while (x)
{
if (x & ) res++;
else
{
if (res & ) return false;
res = ;
} x >>= ;
}
if (res & ) 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, , sizeof (dp));
int tot = ( << m);
for (int i=; i<tot; ++i)
{
if (ok (i)) dp[][i] = ;
} for (int i=; i<=n-; ++i)
{
for (int j=; j<tot; ++j)
{
if (dp[i][j])
{
for (int k=; k<tot; ++k)
{
if ((j | k) == tot - && ok (j & k))
{
dp[i+][k] += dp[i][j];
}
}
}
}
} printf ("%I64d\n", dp[n][tot-]);
} return ;
}
上一篇:ios 性能优化策略


下一篇:win10开启开发人员模式