• 状态压缩学习笔记

    目录

    例题一

    问题描述

    输入格式

    输出格式

    样例输入

    样例输出

    例题二

    问题描述

    输入格式

    输出格式

     例题三

    问题描述

    输入格式

    输出格式

    提示

    例题四

    问题描述

    输入格式

    输出格式

    样例输入

    样例输出

    提示

    例题五

    问题描述

    输入格式

    输出格式

    样例输入

    样例输出

    例题一

    我们先来一道例题：

                                                           传球游戏

    问题描述

    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次方

    代码如下：

    1. #include
    2. using namespace std;
    3. const int INF = 99999999;
    4. const int max2n = 1 << 16 | 5;
    5. const int maxn = 16 + 5;
    6. int dp[max2n][maxn], cont[maxn][maxn], n;
    7. signed main() {
    8. 	ios::sync_with_stdio(false);
    9. 	scanf("%d", &n);
    10. 	for (int i = 0; i < n; i++) {
    11. 		for (int j = 0; j < n; j++) {
    12. 			scanf("%d", &cont[i][j]);
    13. 		}
    14. 	}
    15. 	for (int i = 0; i < (1 << n); i++) {
    16. 		for (int j = 0; j < n; j++) {
    17. 			dp[i][j] = INF;
    18. 		}
    19. 	}
    20. 	for (int i = 0; i < n; i++) {
    21. 		dp[1 << i][i] = 0;
    22. 	}
    23. 	for (int i = 2; i < (1 << n); i++) {
    24. 		for (int j = 0; j < n; j++) {
    25. 			if (i >> j & 1) {
    26. 				for (int k = 0; k < n; k++) {
    27. 					if (j != k && (i >> k & 1)) {
    28. 						dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + cont[k][j]);
    29. 					}
    30. 				}
    31. 			}
    32. 		}
    33. 	}
    34. 	int ans = INF;
    35. 	for (int i = 0; i < n; i++) {
    36. 		ans = min(ans, dp[(1 << n) - 1][i]);
    37. 	}
    38. 	printf("%d", ans);
    39. 	return 0;
    40. }

    例题二

    我们再来一道例题：

                                                                    过桥

    问题描述

    一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制.

    所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.

    队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,

    我们想知道如何分批过桥能使总时间最少.

    输入格式

    第一行两个整数: 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次方

    下面上代码：

    1. #include
    2. using namespace std;
    3. const int INF = 99999999;
    4. const int max2n = 1 << 16 | 5;
    5. int dp[max2n], w[max2n], t[max2n], n, W;
    6. signed main() {
    7. 	scanf("%d%d", &W, &n);
    8. 	for (int i = 0; i < n; i++) {
    9. 		scanf("%d%d", &t[1 << i], &w[1 << i]);
    10. 		dp[1 << i] = t[1 << i];
    11. 	}
    12. 	for (int i = 1; i < (1 << n); i++) {
    13. 		if (i & i - 1) {
    14. 			t[i] = max(t[i & i - 1], t[i & -i]);
    15. 			w[i] = w[i & i - 1] + w[i & -i];
    16. 			if (w[i] <= W) {
    17. 				dp[i] = t[i];
    18. 			} else {
    19. 				dp[i] = INF;
    20. 				for (int j = i - 1 & i; j; j = j - 1 & i) {
    21. 					if (w[j] <= W && dp[i] > dp[i ^ j] + t[j]) {
    22. 						dp[i] = dp[i ^ j] + t[j];
    23. 					}
    24. 				}
    25. 			}
    26. 		}
    27. 	}
    28. 	printf("%d", dp[(1 << n) - 1]);
    29. 	return 0;
    30. }

     例题三

    我们再来看一道例题:

                                                                校长的烦恼

    问题描述

    某中学开设有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

    这道题我们不能状态压缩老师的情况，我们只能压缩课程的情况。

    我们用两个状态表示，第一个状态表示这门课是否有至少一个人上，第二个表示这门课是否有至少两个人上，即可。

    1. #include 
    2. using namespace std;
    3. int s0, n, m, f[125][1 << 8][1 << 8], c[125], b[125];
    4. int main() {
    5. 	scanf("%d %d %d", &s0, &m, &n);
    6. 	memset(f, 0x3f3f, sizeof(f));
    7. 	int s1 = 0, s2 = 0, cnt = 0;
    8. 	for (int k = 1; k <= m; k++) {
    9. 		int c;
    10. 		scanf("%d", &c);
    11. 		cnt += c;
    12. 		string s;
    13. 		getline(cin, s);
    14. 		int num = 0, len = s.length();
    15. 		for (int i = 0; i < len ; i++)
    16. 			if (s[i] >= '0' && s[i] <= '9') {
    17. 				num *= 10, num += s[i] - '0';
    18. 			} else if (num) {
    19. 				if (!(s2 & (1 << (num - 1)))) {
    20. 					if (s1 & ((1 << (num - 1)))) {
    21. 						s1 ^= ((1 << (num - 1))), s2 |= ((1 << (num - 1)));
    22. 					} else {
    23. 						s1 |= ((1 << (num - 1)));
    24. 					}
    25. 				}
    26. 				num = 0;
    27. 			}
    28. 		if (num) {
    29. 			if (!(s2 & (1 << (num - 1)))) {
    30. 				if (s1 & ((1 << (num - 1)))) {
    31. 					s1 ^= ((1 << (num - 1))), s2 |= ((1 << (num - 1)));
    32. 				} else {
    33. 					s1 |= ((1 << (num - 1)));
    34. 				}
    35. 			}
    36. 		}
    37. 	}
    38. 	f[0][s1][s2] = cnt;
    39. 	for (int k = 1; k <= n; k++) {
    40. 		scanf("%d", &c[k]);
    41. 		string s;
    42. 		getline(cin, s);
    43. 		int num = 0, len = s.length();
    44. 		for (int i = 0; i < len ; i++) {
    45. 			if (s[i] >= '0' && s[i] <= '9') {
    46. 				num *= 10, num += s[i] - '0';
    47. 			} else if (num) {
    48. 				b[k] |= (1 << (num - 1)), num = 0;
    49. 			}
    50. 		}
    51. 		if (num) {
    52. 			b[k] |= (1 << (num - 1));
    53. 		}
    54. 	}
    55. 	for (int k = 0; k < n; k++) {
    56. 		for (int i = 0; i < 1 << 8; i++) {
    57. 			for (int j = 0; j < 1 << 8; j++) {
    58. 				if (f[k][i][j] != 0x3f3f3f3f) {
    59. 					f[k + 1][i][j] = min(f[k + 1][i][j], f[k][i][j]);
    60. 					int ss1 = i, ss2 = j;
    61. 					for (int c = 0; c < s0; c++) {
    62. 						if ((!(b[k + 1] & (1 << c))) || (j & (1 << c) )) {
    63. 							continue;
    64. 						}
    65. 						if (i & (1 << c)) {
    66. 							ss1 ^= (1 << c), ss2 |= (1 << c);
    67. 						} else {
    68. 							ss1 |= (1 << c);
    69. 						}
    70. 					}
    71. 					f[k + 1][ss1][ss2] = min(f[k + 1][ss1][ss2], f[k][i][j] + c[k + 1]);
    72. 				}
    73. 			}
    74. 		}
    75. 	}
    76. 	printf("%d", f[n][0][(1 << s0) - 1]);
    77. 	return 0;
    78. }

    例题四

                                                     【状压】玉米地

    问题描述

    Farmer John买了一片土地，可以表示为一片由方块组成的网格，长度为M，宽度为N（1 <= M, N <= 12）。现在FJ要在地里种上一些玉米让他的奶牛们直接在地里食用。FJ知道他的这片土地有些地方很贫瘠，没有办法种玉米；并且奶牛们不喜欢挨在一起吃玉米，所以不能在相邻的两块地上种玉米。请帮助FJ计算一下所有可能的种玉米的方案数。注意，结果输出对于100,000,000的余数，一棵玉米也不中也算是一种方案。

    输入格式

    第一行 两个整数M和N
    接下来是一个M*N的矩阵，1表示该方块可以种玉米，0表示不行

    输出格式

    一个整数，表示对应的结果

    样例输入

    2 3
    1 1 1
    0 1 0

    样例输出

    9

    提示

    把每块能中玉米的地编上号：
    1 2 3 
    0 4 0
    只种一块地，方案有(1, 2, 3, 4)；种两块地方案有 (13, 14, 34)；种三块地 (134), 
    一块也不种也算一种方案，总共4+3+1+1=9

    这道题是一个十字形的状压DP。

    我们可以从上到下去递推，只要知道了第一行的状态，就能推出后面的方案。

    1. #include 
    2. using namespace std;
    3. const int maxn = 1e8;
    4. int n, m, ans, c[13], a[13][13], f[15][1 << 15];
    5. int main() {
    6. 	ios::sync_with_stdio(false);
    7. 	cin >> n >> m;
    8. 	int p = (1 << m) - 1;
    9. 	for (int i = 1; i <= n; i++) {
    10. 		for (int j = 1; j <= m; j++) {
    11. 			cin >> a[i][j];
    12. 			if (a[i][j] == 1) {
    13. 				c[i] = c[i] | (1 << (j - 1));
    14. 			}
    15. 		}
    16. 	}
    17. 	for (int i = 0; i <= p; i++) {
    18. 		if ((i | c[1]) == c[1] && ((i >> 1)&i) == 0 && (i & (i << 1)) == 0) {
    19. 			f[1][i] = 1;
    20. 		}
    21. 	}
    22. 	for (int i = 2; i <= n; i++) {
    23. 		for (int j = 0; j <= p; j++) {
    24. 			for (int k = 0; k <= p; k++) {
    25. 				if ((j | c[i]) == c[i] && (j & k) == 0 && ((j >> 1)&j) == 0 && (j & (j << 1)) == 0) {
    26. 					f[i][j] = (f[i][j] + f[i - 1][k]) % maxn;
    27. 				}
    28. 			}
    29. 		}
    30. 	}
    31. 	for (int i = 0; i <= p; i++) {
    32. 		f[n + 1][0] += f[n][i];
    33. 		f[n + 1][0] %= maxn;
    34. 	}
    35. 	cout << f[n + 1][0];
    36. 	return 0;
    37. }

    例题五

                                     【NOI2001 Day2 T2】炮兵阵地

    问题描述

    司令部的将军们打算在  的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。
     



    在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；
    一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
    如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
    　 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

    输入格式

    第一行包含两个由空格分割开的正整数，分别表示N和M；
    接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。
    N≤100；M≤10。

    输出格式

    仅在第一行包含一个整数K，表示最多能摆放的炮兵部队的数量。

    样例输入

    5 4
    PHPP
    PPHH
    PPPP
    PHPP
    PHHP

    样例输出

    6

    这道题是例题四的加强版。它是将玉米地的十字扩大了一下，所以我们要判左移一位、右移一位、左移两位、右移两位等等，这时候可以考虑在上一题的基础上用离散化（也可以不用）。

    1. #include
    2. using namespace std;
    3. int n, m, cnt, a[105], s[1 << 10], num[1 << 10], f[2][1 << 10][1 << 10];
    4. int main() {
    5. 	ios::sync_with_stdio(false);
    6. 	cin >> n >> m;
    7. 	for (int i = 1; i <= n; i++) {
    8. 		for (int j = 0; j < m; j++) {
    9. 			char c;
    10. 			cin >> c;
    11. 			if (c == 'P') {
    12. 				a[i] += 1 << (m - j - 1);
    13. 			}
    14. 		}
    15. 	}
    16. 	for (int i = 0; i < (1 << m); i++) {
    17. 		if (!(i & i >> 1) && !(i & i >> 2)) {
    18. 			s[cnt++] = i;
    19. 			for (int j = 0; j < m; j++)
    20. 				num[i] += (i >> j & 1);
    21. 		}
    22. 	}
    23. 	f[0][0][0] = 0;
    24. 	for (int i = 1; i <= n + 2; i++) {
    25. 		for (int j = 0; j < cnt; j++) {
    26. 			for (int k = 0; k < cnt; k++) {
    27. 				for (int kk = 0; kk < cnt; kk++) {
    28. 					if (!(s[j]&s[k]) && !(s[j]&s[kk]) && !(s[k]&s[kk]) && (s[j]&a[i]) == s[j] && (s[k]&a[i - 1]) == s[k]) {
    29. 						f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][k][kk] + num[s[j]]);
    30. 					}
    31. 				}
    32. 			}
    33. 		}
    34. 	}
    35. 	cout << f[n + 2 & 1][0][0];
    36. 	return 0;
    37. }
  • 相关阅读:
    助力青少年学习，亚马逊云科技2024年全球人工智能和机器学习奖学金计划正式启动
    【剑指Offer】27.二叉树的镜像
    苹果开发者证书申请流程
    基于Vue+ELement搭建动态树与数据表格实现分页
    Qt——连接mysql增删查改（仓库管理极简版）
    Linux学习6—文件的查找与压缩
    Day 54 前端 jQuery
    B-神经网络模型复杂度分析
    充换电企业开迈斯低成本提升线上应用稳定性的最佳实践
    【漏洞复现】shiro 反序列化 （CVE-2016-4437）
  • 原文地址：https://blog.csdn.net/ny_666/article/details/134058509