啊哈 来写一个状压dp八
状态压缩
状态压缩DP，简称状压DP。
那状态压缩是什么捏？比如我们有一个vis数组，这个数组的第i个元素代表这个元素选或不选。
那比如编号1,4,5的元素选了，0,2,3没有选的vis数组就可以这样表示：
1
2
3
4
5
6
| vis
------------------------------
|key | 0 | 1 | 2 | 3 | 4 | 5 |
|----|---|---|---|---|---|---|
|val | 0 | 1 | 0 | 0 | 1 | 1 |
------------------------------
|
这里vis数组的一系列权值都是0和1。只有0和1有没有让你想起什么？没错，2进制啊！！！
那如果想用一个二进制数表示这个vis数组，就可以这样：
1
2
| ( 1 1 0 0 1 0)
vis[5] vis[4] vis[3] vis[2] vis[1] vis[0]
|
那我们表示这个数组的对应的二进制数就是(010011)2。第i个元素就对应了这个二进制数的从右往左第i位。
至于为什么要从右往左，等你写代码你就会感到方便了。
那现在你对状态压缩是不是有点感觉了？状态压缩就是用一个二进制数来表示当前的状态，因为用数来表示操作会更快捷。
那长度为N的一个二进制数就可以表示N个元素的状态，范围是从0到2n−1，所以在使用状压之前，要看看数据范围能不能容许你数达到2n−1这个大小。
例题
不管怎样，先来几道状压DP的题练练手吧
旅行商
题目
题目描述
beat放假了想要去旅游，他准备去N个城市玩，这些城市分别编号1~N。
beat从1号城市开始，想玩遍所有N个城市，最后回到1号城市。
每个城市之间都可以坐飞机来往，从i号城市到j号城市(1≤i,j≤n)的机票是Ai,j元。Ai,j不一定等于Aj,i。
beat不想重复玩同一个城市，请帮beat规划一种方案，使他花费的钱最少，并给出最少的钱数！
数据范围
对于100%的数据，1≤N≤18，如果i=j，Ai,j=0， 否则1≤Ai,j≤104。
时间限制1秒。
样例
样例输入
样例输出
思路
对于每个城市，我们只有两种状态：去或者没去。分别可以用0和1表示。
注意到N最大到18，非常的小，2n−1最大到262144，然后我们还要枚举最后一次到达的城市是O(N)，那O(2NN)正好能过1秒的时间限制。
我们先考虑状态，dpi,j就表示当前走过的城市状态i，最后一次到达的城市j。
然后考虑转移：
我们第一维枚举去过的城市状态i，i∈[1,2n−1]。
我们第二维和第三维枚举最后一个去过的城市j和下一个要去的城市k，j,k∈[1,n]
现在考虑转移，首先我们要判断两个条件，看看现在的i,j,k能不能存在：
-
dpi,j要存在，你连这个状态都不存在你怎么走到k呢？我们会把dp里的元素全部都变成无穷大，所以只需要判断dpi,j是否小于无穷大就行了。
-
题目说每一个城市不能重复去，所以我们要判断当前状态i中，城市k有没有出现，那就是i >> (k - 1) & 1为0不就行了。那状态i变成去过城市k就是i的第k位要变成1，即新状态为i + (1 << (k - 1))。
那不就可以写出转移方程：
dp[i + (1 << (k - 1))][k] = min(dp[i + (1 << (k - 1))][k], dp[i][j] + a[j][k])
然后我们就做完了！
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, a[19][19], dp[1 << 18][19];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
memset(dp, INF, sizeof(dp));
dp[1][1] = 0;
for (int i = 0; i < (1 << n); i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (dp[i][j] < INF && !(i >> (k - 1) & 1)) {
dp[i + (1 << (k - 1))][k] = min(dp[i + (1 << (k - 1))][k], dp[i][j] + a[j][k]);
}
}
}
}
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = min(ans, dp[(1 << n) - 1][i] + a[i][1]);
}
cout << ans;
return 0;
}
|
祈愿
题目
题目描述
祈愿现在有N个角色池，编号为1到N。每个角色池的大保底为Ai发才能保证出当前池子的角色。
现在beat想要把所有N个角色（其实想要skk）都抱回尘歌壶，但是他的运气实在是太差了，必须不断抽到大保底的次数才能获得当前池子的角色。
老米看他太悲惨了，所以如果他选择把两个池i和j的次数同时抽完，那只需要ai ^ aj的次数就可以大保底了。
beat想知道获得所有角色最少需要抽多少发!
数据范围
2≤N≤20
1≤Ai≤105
样例
样例输入
样例输出
思路
首先对于每个角色池，只有可能抽过和没抽过两种状态，所以又可以用状压dp了，并不难
定义状态：dpi就表示当前状态i的最优方案。
那我们第一维先枚举状态i，然后第二维枚举选择的第一个池j，这里依旧要判定i的第j位不能为1。
那这里的状态更新：
dp[i + (1 << (j - 1))] = min(dp[i + (1 << (j - 1))], dp[i] + a[j]);
题目里也可以同时抽两个池，所以要多一维k，这里k不能等于j，i的第k位也不能是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
| #include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n;
int a[21], dp[1 << 20];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < (1 << n) - 1; i++) {
for (int j = 1; j <= n; j++) {
if ((i >> (j - 1)) & 1) {
continue;
}
dp[i + (1 << (j - 1))] = min(dp[i + (1 << (j - 1))], dp[i] + a[j]);
for (int k = 1; k <= n; k++) {
if (j == k) {
continue;
}
if ((i >> (k - 1)) & 1) {
continue;
}
dp[i + (1 << (j - 1)) + (1 << (k - 1))] = min(dp[i + (1 << (j - 1)) + (1 << (k - 1))], dp[i] + (a[j] ^ a[k]));
}
}
}
cout << dp[(1 << n) - 1];
return 0;
}
|
打游戏
题目
题目描述
需要在学校呆N天的beat喜欢玩原神，如果第i天他玩上了原神，他就会获得Ai点快乐值。
但是学习也很重要虽然没有玩原神重要，beat在连续的M天里，最多只能有一半的天数玩原神，请帮他规划哪几天可以玩原神，然后输出他最大可以获得的快乐值！
数据范围
样例
样例输入
样例输出
