0%

初探状态压缩dp

状压 DP 简介

状压 dp 是动态规划的一种,通过将状态压缩为整数来达到优化转移的目的。

状态 dp 在写题时一般是多维数组,下标即是状态信息,值为答案,然后推出递推方程。

在for中下标即作为循环信息,也作为转移信息。

可以先看数据大小是否可以枚举情况,如果可以,那么只需要考虑在状态i时的递推方程即可

例题:

1.[锁][https://ac.nowcoder.com/acm/problem/14732]

106号房间共有n名居民, 他们每人有一个重要度。房间的门上可以装若干把锁。假设共有k把锁,命名为1到k。每把锁有一种对应的钥匙,也用1到k表示。钥匙可以复制并发给任意多个居民。每个106房间的居民持有若干钥匙,也就是1到k的一个子集。如果几名居民的钥匙的并集是1到k,即他们拥有全部锁的对应钥匙,他们都在场时就能打开房门。新的陆战协定规定,一组居民都在场时能打开房门当且仅当他们的重要度加起来至少为m。问至少需要给106号房间装多少把锁。即,求最小的k,使得可以适当地给居民们每人若干钥匙(即一个1到k的子集),使得任意重要度之和小于m的居民集合持有的钥匙的并集不是1到k,而任意重要度之和大于等于m的居民集合持有的钥匙的并集是1到k。

输入描述:

第一行两个整数n和m,0<n<21,0<m<1000000001。
第二行n个整数表示居民们的重要度。
重要度在[1,1000000000]之间。

输出描述:

一个整数表示最少需要多少把锁。

解析:

对于一个复杂度<m的集合,如果加上集合外的一个最小复杂度后,复杂度>=m的话,称该集合为最小复杂度集合

可以知道任意重要度>=m的集合一定包括一个最小复杂度集合

对于一个最小复杂度集合可以用一种钥匙满足要求,即该集合有一种钥匙,集合外无这种钥匙。类推可以知道,所有包括某个最小复杂度集合任意>=m的集合都可以用同一种分配方式。

所以一个最小复杂度集合需要一种钥匙,我们需要知道任意>=m的集合需要多少种钥匙,问题可以转化成有多少个最小复杂度集合。

因为n<21,所以用状态dp,遍历每一个状态,判断当前状态是否属于最小复杂度集合,属于ans++,否则继续。

代码:

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
#define Oo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
typedef long long ll;
ll n, m, a[40];
int main()
{
Oo
cin>>n>>m;
for (int i=1; i<=n; i++)cin>>a[i];
ll ans=0;
for (int i=0; i< (1<<n); i++)
{
ll temp = 0;
ll mi = INT_MAX;
for (int j=0; j<n; j++)
{
if ((1<<j)&i)temp+=a[j+1];
else mi = min(mi, a[j+1]);
}
if (temp>=m)continue;
else
{
if (temp+mi>=m)ans++;
}
}cout << ans << endl;
return 0;
}

2.[简单环][https://ac.nowcoder.com/acm/problem/16544]

题目描述

给定一张n个点m条边的无向图,求出图中所有简单环的数量。(简单环:简单环又称简单回路,图的顶点序列中,除了第一个顶点和最后一个顶点相同外,其余顶点不重复出现的回路叫简单回路。或者说,若通路或回路不重复地包含相同的边,则它是简单的)

输入描述:

第一行三个数n m k (k在输出描述中提到)
接下来m行每行两个数u,v表示u到v之间存在一条边(无重边)

输出描述:

输出k行每行1个整数
第i个数表示长度%k==i-1的简单环的数量(对998244353取模)
(只记录长度大于2的简单环的数量)

备注:

n<=20
m<=n*(n-1)/2
k<=n

解析:

用状态dp遍历每一个状态,然后以当前状态遍历中间点和终点。

$dp[i][j]$中$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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = (1<<20) + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll dp[maxn][20], ans[22], a[22];
int n, m, K, d[22][22];
int main()
{
scanf("%d %d %d", &n, &m, &K);
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
d[x-1][y-1] = d[y-1][x-1] = 1; //切记状压从第0位开始,所以点也是从0计数
}
for(int i = 0; i < n - 2; i++) //以点 i 为起始点
dp[1<<i][i] = 1;
for(int i = 1; i < (1<<n); i++)
{
int s = 0; //s记录最低位1,即路径的起点
for(;;s++)
if(i & (1<<s))
break;
if(s >= n - 2) continue;
for(int j = s; j < n; j++) //s前面不会有1
{
if(((1<<j) & i) == 0 || dp[i][j] == 0) continue; //找到要扩展出路径的点
for(int k = s + 1; k < n; k++) //找到被扩展的点
{
if(((1<<k) & i) || d[j][k] == 0) continue;
dp[i | (1<<k)][k] += dp[i][j];//
}
if(d[j][s]) //如果可以形成一个环
{
int num = __builtin_popcount(i); //统计1的个数
if(num >= 3)
ans[num] += dp[i][j];
}
}
}
for(int i = 3; i <= n; i++)
a[i%K] = (a[i%K] + ans[i]) % mod;//模
for(int i = 0; i < K; i++)
printf("%lld\n", (a[i] * (mod + 1) / 2) % mod);//求1/2逆元
}