状态压缩Dp第一大类– 连通性问题(棋盘问题)
注:博客新人,自己复习用,问题中不正确处还请大佬们多多指出QWQ
https://www.acwing.com/problem/content/293/
一.思路分析
解法确定:
1.(暴力枚举):我比较菜,使用暴力枚举没有想到如何着手QWQ
2.状压Dp: 题目求数量,属于dp三大属性之一,且数据规模N <= 11, 题材为棋盘类型, 容易推出使用状压Dp
分析易知:对于此题合成大矩形的小矩形一共分为横条与竖条两种,并且有如下结论
所有合法横条的摆放确定后(注意必须是合法的横条摆放好后),竖条的摆放也随之被唯一确定
1.状态表示
dp[i][j]: 表示矩形前i - 1列已经全部摆完, 第i列戳出的横条的排列状态为j的二进制表示的所有方案数
2.状态计算
dp[i][j] += dp[i - 1][k]
j & k == 0
–解决重合问题
我们假设第i列的状态为j,第i - 1列为k
因为1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, 0 & 1 = 0, 只要j中任意二进制位出现1,k的该位就不能出现1保证不重合
故通过 j & k判断
j | k
–解决保证竖条插入问题
0 | 0 = 0, 1 | 0 = 1, 0 | 1 = 1, 1 | 1 = 1
在解决问题1的前提下,j的二进制位为1时,k的二进制位必为0保证不重合,所以通过j 或 k的每一位,可以得到i - 1列的横条排列情况,以此方便下一步计算是否连续0都为偶数
如图
源码
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N = 15, M = 1 << N;
bool st[M]; //当前状态是否合法
vector<int> state[M]; //state[k]:记录i - 1列的状态为k时,第i列的合法状态可以是state[k]中的任意状态
ll dp[N][M]; //dp[i][j]:第i-1列的已经摆好,第i列中戳出状态为j的所有可能状态
int n, m; //问题矩阵长&宽
int main() {
while(cin >> n >> m, n || m) {
//预处理出任意列横条摆好之后是否合法 -- 保证竖条的偶数性
for(int i = 0; i < 1 << n; i ++ ) {
int cnt = 0;
st[i] = true; //新算一个大矩形
for(int j = 0; j < n; j ++ ) {
if(i >> j & 1) {
if(cnt & 1) {
st[i] = false;
break;
} else cnt = 0;
} else cnt ++ ;
}
if(cnt & 1) st[i] = false;
}
//预处理相邻两列所有合法的组合
for(int i = 0; i < 1 << n; i ++ ) {
state[i].clear();
for(int j = 0; j < 1 << n; j ++ ) {
if((i & j) == 0 && st[i | j]) {
state[i].pb(j);
}
}
}
//新算一个大矩形
memset(dp, 0, sizeof dp);
//dp过程
dp[0][0] = 1; //初始化
for(int i = 1; i <= m; i ++ ) {
for(int j = 0; j < 1 << n; j ++ ) { //枚举当前列所有可能的戳出情况
for(auto k : state[j]) { //枚举当前列当前戳出情况的所有合法前一列戳出情况
dp[i][j] += dp[i - 1][k]; //注意边界问题
}
}
}
printf("%lld\n", dp[m][0]);
}
return 0;
}
几个重要的代码块说明
预处理这一列所有合法的状态,保证任意一列在横条插入后能插入竖条
即方便使用 j | k
还原i - 1
列后直接通过st[j | k]
判断i - 1
是否是否能插入竖条
for(int i = 0; i < 1 << n; i ++ ) {
int cnt = 0;
st[i] = true; //新算一个大矩形
for(int j = 0; j < n; j ++ ) {
if(i >> j & 1) {
if(cnt & 1) {
st[i] = false;
break;
} else cnt = 0;
} else cnt ++ ;
}
if(cnt & 1) st[i] = false;
}
预处理相邻两列中即不会有重合的状态也不会导致不能插入竖条的状态,将状态保存在state
数组中
for(int i = 0; i < 1 << n; i ++ ) {
state[i].clear();
for(int j = 0; j < 1 << n; j ++ ) {
if((i & j) == 0 && st[i | j]) {
state[i].pb(j);
}
}
}
dp[0][0] = 1
dp[0][0]:指0之前的所有列已经摆好,戳出状态为0的方案数,显然只有一种
同时dp[0][j] == 0,且j > 0
,因为0列前面不存在任意列,戳出状态除了0以外的任何状态都不可能出现,故方案数都为0
dp[m][0]
结果输出dp[m][0]
,从定义出发,dp[m][0]表示m - 1(我们以0列作为第一列)已经摆好,且在m中戳出状态为0的所有方案数