学习笔记"/>
状态压缩学习笔记
我们先来一道例题：
传球游戏
问题描述
n个人在做传球的游戏,编号为1-n。
游戏规则是这样的：开始时球可以在任意一人手上，他可把球传递给其他人中的任意一位；下一个人可以传递给未接过球的任意一人。
即球只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；
求当球经过所有n个人后，整个过程的最小总代价是多少。输入格式
第一行为n,表示共有n个人（16>=n>=2）；
以下为n*n的矩阵，第i+1行、第j列表示球从编号为i的人传递到编号为j的人所花费的代价，特别的有第i+1行、第i列为-1（因为球不能自己传给自己），其他数据均为正整数(<=10000)。输出格式
一个数，为最小的代价总和。
样例输入
样例输入1： 2-1 9794 2724 –1样例输入2： 4-1 4551 3763 4873 4465 -1 9323 2204 705 2102 -1 333 9264 5206 2596 -1样例输出
样例输出1：
2724
样例输出2：
5505
我们以这道题来讲解。n小于等于16，所以dfs搜索肯定会TLE，排除。
我们可以考虑状态压缩DP：
我们先开一个二维数组dp[i][j]，i表示第i个人是否接过球，j表示第j个人，dp[i][j]表示代价。
那么以第j个人结束的方案数的值就出来了，状态转移方程如下：
dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + cont[k][j]);然后再遍历n个人，取他们的最小值。时间复杂度是n方乘上2的n次方
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF = 99999999;
const int max2n = 1 << 16 | 5;
const int maxn = 16 + 5;
int dp[max2n][maxn], cont[maxn][maxn], n;
signed main() {ios::sync_with_stdio(false);scanf("%d", &n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {scanf("%d", &cont[i][j]);}}for (int i = 0; i < (1 << n); i++) {for (int j = 0; j < n; j++) {dp[i][j] = INF;}}for (int i = 0; i < n; i++) {dp[1 << i][i] = 0;}for (int i = 2; i < (1 << n); i++) {for (int j = 0; j < n; j++) {if (i >> j & 1) {for (int k = 0; k < n; k++) {if (j != k && (i >> k & 1)) {dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + cont[k][j]);}}}}}int ans = INF;for (int i = 0; i < n; i++) {ans = min(ans, dp[(1 << n) - 1][i]);}printf("%d", ans);return 0;
}我们再来一道例题：
过桥
问题描述
一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制.
所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.
队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,
我们想知道如何分批过桥能使总时间最少.输入格式
第一行两个整数: w，n 分别表示 桥能承受的最大重量(100 <= w <= 400) 和 n 队员总数(1 <= n <= 16).
接下来n 行每行两个整数t和w分别表示每个队员过桥所需时间(1 <= t <= 50) 和 该队员的重量(10 <= w <= 100).输出格式
输出一个数表示最少的过桥时间.
样例输入 1
100 3
24 60
10 40
18 50样例输出 1
42
样例输入 2
150 5
50 44
40 33
35 36
30 75
11 76样例输出 2
90
这道题也是状压DP，只不过要枚举子集。先输入w和n然后对dp[i]作初始化。如果这个子集重量没有超过桥的重量限制，就直接处理，将dp[i]=t[i]，否则对自己进行拆分。时间复杂度是3的n次方
下面上代码：
#include<bits/stdc++.h>
using namespace std;
const int INF = 99999999;
const int max2n = 1 << 16 | 5;
int dp[max2n], w[max2n], t[max2n], n, W;
signed main() {scanf("%d%d", &W, &n);for (int i = 0; i < n; i++) {scanf("%d%d", &t[1 << i], &w[1 << i]);dp[1 << i] = t[1 << i];}for (int i = 1; i < (1 << n); i++) {if (i & i - 1) {t[i] = max(t[i & i - 1], t[i & -i]);w[i] = w[i & i - 1] + w[i & -i];if (w[i] <= W) {dp[i] = t[i];} else {dp[i] = INF;for (int j = i - 1 & i; j; j = j - 1 & i) {if (w[j] <= W && dp[i] > dp[i ^ j] + t[j]) {dp[i] = dp[i ^ j] + t[j];}}}}}printf("%d", dp[(1 << n) - 1]);return 0;
}校长的烦恼
问题描述
某中学开设有s门课程，现有教师m个。今天有n个求职者来应聘新教师。
已知每个人工资和能教授的课程。
在职教师不能辞退，校长想知道，最少支付多少工资就能使得每门课都有至少两名教师能教。输入格式
第一行，三个整数s,m和n
接下来m行，每行若干个整数，描述一名在职教师的情况：第一个整数，表示该教师的工资，接下来的若干整数表示该教师能教的课程；
接下来n行，每行若干个整数，描述一名求职者的情况：第一个整数，表示该求职者要求的工资，接下来的若干整数表示该求职者能教的课程；
注意，每行末尾有空格
输出格式
一行，一个整数，表示所求结果。
若无解，输出-1样例输入 1
2 2 2
10000 1
20000 2
30000 1 2
40000 1 2样例输出 1
60000
样例输入 2
5 2 4
24 2 4
39 4 1
9 4
81 2 1 5
19 2 3 5
65 3 1样例输出 2
228
提示
1<=s<=8
1<=m<=20
1<=n<=100
1<=每个人的工资<=50000
1<=每个人教的课的编号<=s
更多推荐
状态压缩学习笔记
发布评论