AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
Ocean_
,
2024-04-08 16:30:06
,
所有人可见
,
阅读 2
状态压缩DP
蒙德里安的梦想
题目描述
算法解释
/*
关于题目的基本认识:
长方块的放置方式只有两种,横着的块放置完以后,竖着的块只有一种放置方式
故只需考虑横放的方案
总方案数等于只放横着的长方块的合法方案数
判断方案合法的方法:
1.所有剩余位置,能否填充满竖直的长方块
2.按列来看,每一列内部所有连续的空着的小方块数,需要是偶数个
*/
/*
dp分析:
f[i][j]: 表示已经将前i-1列摆好,且从第i-1列,伸出到第i列状态为j的所有方案数
j为二进制数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL; // 方案的总数多
const int N = 12, M = 1 << N; // Step3考虑,棋盘若有11列,则需要知道f[12][]的值
int n, m;
LL f[N][M]; // 最多N列,每列的状态最多1 << 行数(N),即二进制表示的范围
// 由于前i-1列已经摆好,故需按照前i-1列的摆放方式划分f[i][j]集合
vector<int> state[M]; // 对于每一列来说,考虑从i-2列到i-1列的合法延伸方式;每一列仍用二进制状态表示
bool st[M]; // 判断每一列的二进制状态是否合法,即连续个0的个数是否为偶数个(用于填充竖方块)
int main()
{
while (cin >> n >> m, n || m) // 逗号表达式,整个式子的真值是第二个式子的真值(n、m都为0退出)
{
/*
Step1: 初始化st[M]
方法:判断连续个0的个数是否为偶数个
结果:可存储所有合法的列状态方案
*/
for (int i = 0; i < 1 << n; i ++ ) // 枚举每一列的所有二进制状态(用十进制表示)
{
int cnt = 0;
bool is_valid = true;
for (int j = 0; j < n; j ++ ) // 枚举每一个二进制状态的所有位(共n位)
if (i >> j & 1) // 第j位若为1,则要判断该位前面的连续个值为0的位数是否为偶数
{
if (cnt & 1) // 若前面连续个0的个数为奇数个
{
is_valid = false; // 不合法,因为竖着的长方块长度为2
break; // 只要有1位不满足就结束该二进制状态的判断
}
cnt = 0; // 该位合法后,连续0的数量要重置
}
else cnt ++ ; // 第j位若为0,则连续0的个数+1
if (cnt & 1) is_valid = false; // 因为每次判断的都是1前面的连续0,故最后可能会剩下一组连续0
st[i] = is_valid; // 记录该二进制状态的合法性
}
/*
Step2: 初始化state[M]
方法:从i-2到i-1的延伸不能与从i-1到i的延伸行冲突;
从i-2到i-1、i-1到i延伸后,第i-1列的二进制状态是否合法(用st[i | j]判断)
注:'|'操作可合并二进制状态
结果:可存储所有相邻合法延伸的方案数
*/
for (int i = 0; i < 1 << n; i ++ ) // 枚举每一列的所有二进制状态(用十进制表示)
{
state[i].clear(); // 保证每一列初始化时都重置
for (int j = 0; j < 1 << n; j ++ ) // 枚举该列的左相邻列的二进制状态
// i & j == 0表示两列的二进制状态每一位都只会是(1,0)、(0,1)、(0,0),即不会产生行冲突
// st[i | j]表示从i-2到i-1、i-1到i延伸后,第i-1列的二进制状态是否合法
if ((i & j) == 0 && st[i | j])
state[i].push_back(j); // 存储第i列的其中一个合法相邻列状态j
}
/*
Step3: dp计算
*/
memset(f, 0, sizeof f); // 将每一种棋盘的放置方案数置0
f[0][0] = 1; // 若棋盘只有一列则只有一种摆放方式
for (int i = 1; i <= m; i ++ ) // 枚举棋盘的每一列(从第二列开始枚举)
for (int j = 0; j < 1 << n; j ++ ) // 枚举每一列的所有二进制状态
for (auto k: state[j]) // 取得相邻的合法延伸方案
f[i][j] += f[i - 1][k];
// 棋盘列编号为0~m-1
cout << f[m][0] << endl; // 表示前m-1列已经摆好,且从第m-1列不伸出到第m列
}
return 0;
}