状态压缩DP
连通性问题
一、核心思想:
- 核心:先放横着的,再放竖着的
- 总方案数等于只放横着的小方块的合法方案数。
- 如何判断当前方案是否合法?
- 所有剩余位置,能否填充满竖着的小方块,需要是偶数个
二、方法:
化零为整 ==> 化整为零
- 状态表示(化零为整):某一个状态表示某一类方案
f[i][j]
表示已经将前i-1
列摆好,且从第i-1
列伸出到第i
列的方案- 任何一个方块不会再摆到前
i-1
列内的任何一个位置 - 从
i-1
列伸到i
列的方案
- 任何一个方块不会再摆到前
- 状态计算(化整为零):分割使得每一个部分可以被计算出来
- 分割依据:最后一步操作
- 第
i-1
列至第i
列的情况已经固定(f[i][j]
),从第i-2
列至第i-1
列的情况(f[i -1][k]
)没有固定,共有\(2^n\)种情况(每一行都有伸或不伸两种情况) - 针对这\(2^n\)种情况,判断能否构成合法方案
j & k == 0
:相邻三列内同一行不能两个小方块i-1
列空着的位置能够填充竖着的小方块,即个数为偶数
- 最终答案
f[m,0]
,前m-1
列摆好了,并且没有任何一个小方块伸到m
列
- 第
- 分割依据:最后一步操作
三、优化
预处理合法状态:对每个状态j
而言,有哪些状态k
可以更新到j
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
//M = 2 ^ N
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M]; //状态转移方程
vector<int> state[M]; //存储所有合法状态
//判断某个状态是否合法,当前列空着的连续位置(0)是否为偶数
bool st[M];
int main() {
while (cin >> n >> m, n || m) {
//预处理
for (int i = 0; i < 1 << n; i ++ ) {
int cnt = 0; //表示0的个数
bool is_valid = true; //表示是否合法
for (int j = 0; j < n; j ++ ) //每行有n个数
if (i >> j & 1) { //如果当前这一位是1
if (cnt & 1) { //有连续奇数个0
is_valid = false;
break;
}
// cnt = 0;
}
else cnt ++;
//判断最后一个0
if (cnt & 1) is_valid = false;
st[i] = is_valid;
}
//枚举所有合法状态
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]) // i | j 为所有塞满的位置
state[i].push_back(j); //存入j到i的合法方案
}
memset(f, 0, sizeof f);
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];
cout << f[m][0] << endl;
}
return 0;
}
标签:状态,cnt,48,小方块,合法,int,算法,include,DP
From: https://www.cnblogs.com/I-am-Sino/p/16990013.html