POJ 2411 Mondriaan's Dream 状态压缩DP
思路
用二进制表示当前行的状态， 0表示这个位置是空的， 1表示当前位置是填充了的， 而且会在i + 1行的这个位置填充上， 即是这个位置存在一个1X2的小矩形， 且这是这个矩形的上半部 上一行的状态 k, 这一行的状态j ， 满足要求的状态为 1： i & k = 0 2：i | k 的值的连续的0的个数为偶数#include
#include
#include
#include
using namespace std;
const int N = 12, M = 11;
typedef long long ll;
ll f[N][1 << M];
bool is_odd[1 <> n >> m && n)
{
//1 ---- 找出0的连续个数是偶数的合法状态
for(int i = 0; i < 1 << m; i++)
{
int cnt = 0;
bool odd = true;
for(int j = 0; j > j & 1)
{
if(cnt & 1)
{
odd = false;
break;
}
else cnt = 0;
}
else cnt++;
}
if(cnt & 1)
odd = false;
is_odd[i] = odd;
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j < 1 << m; j++)
for(int k = 0; k < 1 << m; k++)
{
if((j & k) == 0 && is_odd[j | k])
f[i][j] += f[i - 1][k];
}
printf("%lld\n", f[n][0]);
}
return 0;
}
作者：正月看雪花
