题目描述
蒙德里安的梦想
样例
略
算法1
(压缩DP)
-
所谓的状态压缩DP,就是用二进制数保存状态。为什么不直接用数组记录呢?因为用一个二进制数记录方便作位运算。前面做过的八皇后,八数码,也用到了状态压缩。
-
本题等价于找到所有横放 1 X 2 小方格的方案数,因为所有横放确定了,那么竖放方案是唯一的。
- 通过预处理符合要求的方案数来进行优化,通过外for循环,来遍历每一个方案,内循环要求方案的每个位置连续的0必须是偶数
- 然后外循环是状态j的方案数,内循环是状态k的方案数,将符合要求的方案添加到j中来组合成总的j
- 最后外循环是m列,满的其实是m-1列,对应没有伸到m列,其中第0列也是初始化为1,表示横着放的都是空,全为竖着放,内循环是方案数j,最内层是状态k。
C++ 代码
#include<bits/stdc++.h>//先横着放,再竖着放,最后方案数是横着放的方案数
using namespace std;
const int N=12;
const int M=1<<N;
long long int f[N][M];
vector<int>statue[M];
bool st[M];
int n,m;
int main()
{
while(cin>>n>>m,n||m)
{
for (int i = 0; i < 1 << n; i ++ )//判断每个方案里的连续空余的部分是不是偶数
{//i为每一个方案
int cnt = 0;//每个方案连续0的个数
bool is_valid = true;//方案符合
for (int j = 0; j < n; j ++ )//n个位置,即行数
if (i >> j & 1)//第j个位置是1
{
if (cnt & 1)//判断j以前的连续0个数是不是偶数
{
is_valid = false;//奇数
break;//这个方案不符合
}
cnt = 0;//是的话清空,方便从j往后数
}
else cnt ++ ;//否则将0的个数迭加
if (cnt & 1) is_valid = false;//最后是奇数,不符合
st[i] = is_valid;//否则方案符合
}
//j方案是由k方案组合而成
for (int i = 0; i < 1 << n; i ++ )//j个方案
{
statue[i].clear();//每个方案里的k
for (int j = 0; j < 1 << n; j ++ )//k个方案
if ((i & j) == 0 && st[i | j])//k,j没有重合的并且方案符合
statue[i].push_back(j);//那就把k方案加入到j中
}
memset(f, 0, sizeof f);//初始化状态数组
f[0][0] = 1;//空地图,代表都是竖着放的就有1种情况
for (int i = 1; i <= m; i ++ )//m-1即为满,枚举到m列
for (int j = 0; j < 1 << n; j ++ )//每一列的j方案数
for (auto k : statue[j])//枚举j中的k,因为j是由k组成的
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;//输出m-1列放满了,从m-1到m没有伸出来的方块了
}return 0;
}