第六课：状态压缩DP/子集枚举
🔗 引用站外地址，请注意甄别
第六课：状态压缩DP/子集枚举
517coding
已知一个状态压缩的数 $i$，有如下操作：
求 $i$ 的第 $j$ 位是否为 $1$ ：i&(1<<j)!=0 （注意：是 !=0，而不是==1）
把 $i$ 的第 $j$ 位修改为 $1$：i|=1<<j
A：环游世界
🔗 引用站外地址，请注意甄别
首先，这很明显是一个无向图
这样，我们需要的信息就是：
- 已走过的点集
- 当前停留在哪里
- 当前的最小花费
知道了这三个信息之后，转移时只要枚举一个未走过的点，从当前的位置转移过去，再把花费加上即可
在做最短路是通常不会主动去构造一个环，而本题要求从起点出发，再回到起点
我们可以先找到一个点 $T$ ，求出起点到 $T$ 的最短路，最后再单独加上 $T$到起点的距离
表示已走过的集合就可以用状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <cstdio>
#include <cstring>
#define min(a, b) (a<b?a:b)
int mp[12][12];
int dp[1 << 12][12];
int n;
void checkmin(int &x, int y) {x == -1 || y < x ? x = y: x = x;}
void input() {
scanf("%d", &n);
n++;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &mp[i][j]);
}
void floyd() {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
void change() {
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
for (int mask = 1; mask < (1 << n); mask++) {
for (int end = 0; end < n; end++) if (dp[mask][end] != 0x3f3f3f3f) {
for (int nxt = 0; nxt < n; nxt++) if (!(mask & (1 << nxt))) {
checkmin(dp[mask | (1 << nxt)][nxt], dp[mask][end] + mp[end][nxt]);
}
}
}
}
void print() {
int ans = 0x3f3f3f3f;
for (int end = 0; end < n; end++) {
checkmin(ans, dp[(1 << n) - 1][end] + mp[end][0]);
}
printf("%d\n", ans);
}
int main() {
input();
floyd();
change();
print();
return 0;
}
|
B：数字重排
🔗 引用站外地址，请注意甄别
观察到 $n$ 最大只有 $16$
那么就可以使用状态压缩
共有两个信息：数字、位置
暴力
$dp_{i_j}$ 中 $i$ 表示放了那哪些位置，$j$ 表示放了哪些数字
接着枚举一个空的位置，进行转移
但是这样的话就要开大小为 $2^{16}\times2^{16}$ 个数组，也就是 $2^{32}$ 个
状态压缩
$dp_{ij}$ 中 $i$ 表示放了数字的集合，$j$ 表示以谁结尾
这时候位置就不重要了，因为当我们可以直接从左往右依次放进去，只需要考虑结尾即可，不用管位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <cstdio>
#include <cstring>
const int N = 18;
const int INF = (int) 1e9;
int a[N], p[N], b[N];
int dp[1 << N][N];
void checkmax(int &x, int y) {if (y > x) x = y;}
int main() {
int n; scanf("%d", &n);
memset(b, -1, sizeof(b));
for (int i = 0; i < n; i++) {scanf("%d%d", &a[i], &p[i]); if (p[i] != -1) b[p[i]] = 1;}
for (int i = 0; i < (1 << n); i++) for (int j = 0; j < n; j++) dp[i][j] = -INF;
if (b[0]) for (int i = 0; i < n; i++) if (p[i] == 0) dp[1 << i][i] = 0;
else for (int i = 0; i < n; i++) if (p[i] == -1) dp[1 << i][i] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int pos = 0;
for (int i = 0; i < n; i++) if (mask & (1 << i)) pos++;
for (int end = 0; end < n; end++) if (dp[mask][end] != -INF)
for (int nxt = 0; nxt < n; nxt++) if (!(mask & (1 << nxt)))
if (p[nxt] == -1 || p[nxt] == pos) checkmax(dp[mask | (1 << nxt)][nxt], dp[mask][end] + a[end] * a[nxt]);
}
int ans = -INF;
for (int end = 0; end < n; end++) checkmax(ans, dp[(1 << n) - 1][end]);
printf("%d\n", ans);
return 0;
}
|
C：开门迷宫
🔗 引用站外地址，请注意甄别
广搜 + 状压DP即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 60;
int n,m,p,k,s;
int x1,y1,x2,y2,x;
int mp1[N][N][N][N], mp2[N][N],vis[N][N][1<<11];
int dx[]= {0,0,1,-1};
int dy[]= {1,-1,0,0};
struct node {
int x,y,key,step;
};
queue<node>q;
int bfs() {
q.push({0,0,0,0});
vis[0][0][0] = 1;
while(!q.empty()) {
node f = q.front(); q.pop();
if(f.x == n - 1 && f.y == m - 1) return f.step;
if(mp2[f.x][f.y] >= 1) f.key += mp2[f.x][f.y] - (mp2[f.x][f.y] & f.key);
for (int i = 0; i < 4; i++) {
int ax = f.x + dx[i];
int ay = f.y + dy[i];
if(ax >= 0 && ax < n && ay >= 0 && ay < m) {
int tmp = mp1[f.x][f.y][ax][ay];
if(tmp == -1 || (tmp>= 1 && (f.key & (1 << tmp)))) {
if(!vis[ax][ay][f.key]) {
q.push({ax,ay,f.key,f.step+1});
vis[ax][ay][f.key]=1;
}
}
}
}
}
return -1;
}
int main() {
scanf("%d%d%d%d", &n, &m, &p, &k);
memset(mp1, -1, sizeof(mp1));
memset(mp2, 0, sizeof(mp2));
for (int i = 1; i <= k; i++){
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &x);
mp1[x1 - 1][y1 - 1][x2 - 1][y2 - 1] = mp1[x2 - 1][y2 - 1][x1 - 1][y1 - 1]=x;
}
scanf("%d", &s);
for (int i = 1; i <= s; i++) {
scanf("%d%d%d", &x1, &y1, &x);
if(x != 0) mp2[x1 - 1][y1 - 1] += 1 << x;
}
int ans = bfs();
printf("%d\n", ans);
return 0;
}
|
E：回文子序列删除
🔗 引用站外地址，请注意甄别
$1$ 个状态可以由多个状态转移过来，那么可以可以转移过来的状态构成了一个子集
$dp_i$ 表示 $i$ 状态的字符集合最少需要删几次
枚举这个状态的回文子集，然后扔掉
假设枚举的回文子集为 $s$ ，那么 $dpi$ 就可以由 $dp{i-s}+1$ 在转移过来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
const int N = 18;
const int INF = (int) 1e9;
char s[N];
int dp[1 << N], flag[1 << N], n;
std::vector<int> v;
bool judge(int mask) {
v.clear();
for (int i = 0; i < n; i++) if (mask & (1 << i)) v.push_back(i);
int l = 0, r = (int) v.size() - 1;
while (l <= r) {
if (s[v[l]] != s[v[r]]) return false;
l++, r--;
}
return true;
}
int main() {
scanf("%s", s);
n = strlen(s);
for (int i = 1; i < (1 << n); i++) {
if(judge(i)) dp[i] = 1, flag[i] = 1;
else dp[i] = INF;
}
for (int mask = 0; mask < (1 << n); mask++)
for (int sub = mask; sub > 0; sub = mask & (sub - 1)) if (flag[sub]) dp[mask] = std::min(dp[mask], dp[mask - sub] + 1);
printf("%d\n", dp[(1 << n) - 1]);
return 0;
}
|
【提高组】第六课：状态压缩DP/子集枚举 学习笔记
