经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
[DP] DP优化总结
来源：cnblogs　　作者：Peppa_Even_Pig　　时间：2024/6/12 19:13:59　　对本文有异议

写在前面

$ DP $，是每个信息学竞赛选手所必会的算法，而 $ DP $ 中状态的转移又显得尤为关键。本文主要从状态的设计和转移入手，利用各种方法对朴素 $ DP $ 的时间复杂度和空间复杂度进行优化与处理，以达到满足题目要求的目的；

参考文献：
动态规划算法的优化技巧 毛子青
c++ DP总结
《算法竞赛进阶指南》

一. 环形与后效性处理

我们都知道，一个题能用 $ DP $ 来解，需要满足以下两个性质：

  1. 无后效性
  2. 最优子结构

但对于有些题目，如果要用 $ DP $ 解决的话，会出现环形与后效性的问题；

所谓环形与后效性，即状态的转移与 $ DP $ 的方向并不完全一致；

举个例子，状态的转移可以从左到右，也可以从右到左，但 $ DP $ 的方向只能为从左到右或从右到左，此时称此 $ DP $ 为有后效性；

当状态初能够由状态末转移而来（此时构成了一个环形）时，此时称此 $ DP $ 为环形；

对于前者的处理，我们通常会改变 $ DP $ 的遍历方向，使其能够与状态转移的方向一致，当无法一致时，可以使用迭代的方法取得最优解；

对于后者，我们通常对初始状态分类讨论，找出几种不是环形的 $ DP $，破环成链，分别处理，最后取最优解；

例题

后效性

Luogu CF24D Broken robot

本题的高斯消元处理 $ DP $ 解法不再叙述，考虑 迭代 $ DP $；

设 $ f[i][j] $ 表示从最后一行走到点 $ (i, j) $ 所需的期望步数，则有状态转移方程：

\[\begin{equation} f[i][j] \begin{cases} \frac{f[i][1] + f[i + 1][1]}{2} + 1 \ (m = 1) \\frac{f[i + 1][j] + f[i][j + 1] + f[i][j]}{3} + 1 \ (j == 1) \\frac{f[i][j - 1] + f[i + 1][j] + f[i][j]}{3} + 1 \ (j = m) \\frac{f[i][j] + f[i + 1][j] + f[i][j - 1] + f[i][j + 1]}{4} + 1 \ (其他情况) \\end{cases} \end{equation} \]

显然，我们 $ DP $ 的方向是向上的，但状态转移的方向是上下左右都有的，所以有后效性，要迭代；

  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstring>
  4. using namespace std;
  5. int n, m;
  6. int xx, yy;
  7. double f[1005][1005];
  8. int main() {
  9. 	cin >> n >> m;
  10. 	cin >> xx >> yy;
  11. 	if (xx == n) {
  12. 		cout << "0.0000000000";
  13. 		return 0;
  14. 	}
  15. 	for (int i = n - 1; i >= xx; i--) {
  16. 		int tt = 65;
  17. 		while(tt--) {
  18. 			if (m == 1) {
  19. 				f[i][1] = 0.5 * f[i][1] + 0.5 * f[i + 1][1] + 1;
  20. 			} else {
  21. 				for (int j = 1; j <= m; j++) {
  22. 					if (j == 1) {
  23. 						f[i][j] = 1.0 / 3 * f[i + 1][j] + 1.0 / 3 * f[i][j + 1] + 1.0 / 3 * f[i][j] + 1;
  24. 					} else if (j == m) {
  25. 						f[i][j] = 1.0 / 3 * f[i][j - 1] + 1.0 / 3 * f[i + 1][j] + 1.0 / 3 * f[i][j] + 1;
  26. 					} else {
  27. 						f[i][j] = 0.25 * f[i][j] + 0.25 * f[i + 1][j] + 0.25 * f[i][j - 1] + 0.25 * f[i][j + 1] + 1;
  28. 					}
  29. 				}
  30. 			}
  31. 		}
  32. 	}
  33. 	cout << fixed << setprecision(4) << f[xx][yy];
  34. 	return 0;
  35. }

环形

Luogu P6064 Naptime G

设计状态 $ f[i][j][k] $ 表示在每 $ N $ 个小时的前 $ i $ 个小时中，休息 $ j $ 个小时，且第 $ j $ 个小时的状态( $ 0 $ 代表醒， $ 1 $ 代表睡)，则：

如果我们直接转移的话，初始状态的睡或不睡会影响后面的转移（环形），所以分类讨论：

  1. 当初始状态为醒的时候（正常转移）：

\[ f[i][j][0] = \max(f[i - 1][j][0], f[i - 1][j][1]) \]

\[ f[i][j][1] = \max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + a[i]) \ (j \neq 0) \]

其中

\[f[0][0][0] = 0 \]

  1. 当初始状态为睡的时候（此时要将初始休息的时间算上）：

\[f[i][j][0] = \max(f[i - 1][j][0], f[i - 1][j][1]) \]

\[f[i][j][1] = \max(f[i - 1][j - 1][0], f[i - 1][j - 1][1] + a[i]) \ (j \neq 0) \]

其中

\[f[1][1][1] = a[1]; \]

最后将两个答案合并起来即可；

可以发现，对于环形的分类讨论，状态转移方程基本一样，但初始化会有差异；

另外，此题有空间的限制，需要把 $ f $ 数组的第一维用滚动数组滚掉；

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. int n, b;
  5. int a[10000005];
  6. int f[2][3831][2]; //0醒, 1睡;
  7. int f1[2][3831][2];
  8. int main() {
  9. 	cin >> n >> b;
  10. 	for (int i = 1; i <= n; i++) {
  11. 		cin >> a[i];
  12. 	}
  13. 	memset(f, 0xcf, sizeof(f));
  14. 	memset(f1, 0xcf, sizeof(f1));
  15. 	f[0][0][0] = 0;
  16. 	for (int i = 1; i <= n; i++) {
  17. 		for (int j = 0; j <= b; j++) {
  18. 			if (j > i) continue;
  19. 			f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
  20. 			f[i & 1][j][1] = max(f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + a[i]);
  21. 			if (j == 0) f[i & 1][j][1] = 0xcfcfcfcf;
  22. 		}
  23. 	}
  24. 	f1[1][1][1] = a[1];
  25. 	for (int i = 2; i <= n; i++) {
  26. 		for (int j = 0; j <= b; j++) {
  27. 			if (j > i) continue;
  28. 			f1[i & 1][j][0] = max(f1[(i - 1) & 1][j][0], f1[(i - 1) & 1][j][1]);
  29. 			f1[i & 1][j][1] = max(f1[(i - 1) & 1][j - 1][0], f1[(i - 1) & 1][j - 1][1] + a[i]);
  30. 			if (j == 0) f1[i & 1][j][1] = 0xcfcfcfcf;
  31. 		}
  32. 	}
  33. 	cout << max(max(f[n & 1][b][0], f[n & 1][b][1]), f1[n & 1][b][1]);
  34. 	return 0;
  35. }

二. 倍增优化

倍增优化的关键是找出一个可以随意划分的状态，最后对状态进行拼接得到答案；

所谓随意划分，即此状态可以拆分成任意多个长度为 $ 2^n $ 的子状态，且拼接时任意两个子状态不互相影响，并且最后的答案就是要求的正确答案；

为什么一个状态能够随意划分成任意多个长度为 $ 2^n $ 的子状态？

对于任意一个正整数，我们可以给他转变成一个二进制数，我们知道，一个二进制数可以表示成 $ 2 $ 的很多次方相加，所以可以；

例题

Luogu P1081 [NOIP2012 提高组] 开车旅行

本题有三个关键信息：已行驶的天数，所在城市，小A和小B各自行驶的路程长度；

若已知出发城市与天数，即可求得小A和小B各自行驶的路程长度，并且依据题意，天数还能反映谁现在在开车，所以我们可以把“天数” 作为“阶段”进行状态设计；

定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发，两人共行驶 $ i $ 天，$ k $ 先开车，最终会到达的城市；

很显然，这样开会炸内存，而天数又可以随意划分，可以考虑倍增优化；

重定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发，两人共行驶 $ 2^i $ 天，$ k $ 先开车，最终会到达的城市；

其中 $ 0 $ 代表小A先开车， $ 1 $ 代表小B先开车；

对于初始化，我们现在知道谁先开车，要求到那个城市，只需知道小A或小B在某一个城市时，下一个会到哪里即可，可以预处理出两个数组 $ ga[i] $ 和 $ gb[i] $ 分别表示小A在城市 $ i $ 时，下一个会到哪个城市和小B在城市 $ i $ 时，下一个会到哪个城市；

对于问题 $ 2 $，我们可以同时维护两个数组 $ da[i][j][k] $ 和 $ db[i][j][k] $ 分别表示从城市 $ j $ 出发，两人共行驶 $ 2^i $ 天，$ k $ 先开车，小A行驶的路程总长度以及小B行驶的路程总长度；

对于问题 $ 1 $，我们只需枚举出发点，找最小的即可；

则：

  1. 对于预处理

因为小A和小B只能往后走，所以我们可以从后往前遍历，并同时维护一个单调递增的序列（可以用 $ multiset $）其实应该是平衡树，但我不会，每次只需找当前节点旁边一位或两位的最小值和次小值即可（建议参考下面的代码）；

  1. 对于初始化

\[f[0][j][0] = ga[j] \]

\[f[0][j][1] = gb[j] \]

  1. 对于状态转移方程

\[f[1][j][k] = f[0][f[0][j][k]][1 - k] \]

\[f[i][j][k] = f[i - 1][f[i - 1][j][k]][k] \ (i \neq 1) \]

  1. 对于 $ da $ 和 $ db $ 的初始化

\[da[0][j][0] = dis[j][ga[j]] \]

\[da[0][j][1] = 0 \]

\[db[0][j][0] = 0 \]

\[db[0][j][1] = dis[j][gb[j]] \]

对于 $ dis $ 的维护，可以在维护单调递增的序列同时顺便维护；

  1. 对于$ da $ 和 $ db $的状态转移方程

\[da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k] \ (i = 1) \]

\[da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k] \ (i > 1) \]

\[db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k] \ (i = 1) \]

\[db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k] \ (i > 1) \]

这里 $ i = 1 $ 时不同，因为 \(2^1\) 只能拆成两个$ 2^0 $ ，$ 2^0 = 1 $ 是奇数，开车的人不同，其它的是偶数，开车的人相同；

  1. #include <iostream>
  2. #include <set>
  3. #include <cmath>
  4. using namespace std;
  5. int n;
  6. int h[10000005];
  7. int x0, m;
  8. struct sss{
  9. 	long long id, he;
  10. 	bool operator <(const sss &A) const {
  11. 		return he < A.he;
  12. 	}
  13. };
  14. long long f[18][100005][2]; // 0 a, 1 b;
  15. long long da[18][100005][2];
  16. long long db[18][100005][2];
  17. multiset<sss> p;
  18. void init() {
  19. 	p.insert({0, 9999999999999999});
  20. 	p.insert({0, 9999999999999999});
  21. 	p.insert({n + 1, -9999999999999999});
  22. 	p.insert({n + 1, -9999999999999999}); //防止访问越界
  23. 	for (long long i = n; i >= 1; i--) {
  24. 		long long ga, gb;
  25. 		p.insert({i, h[i]});
  26. 		multiset<sss>::iterator q = p.lower_bound({i, h[i]});
  27. 		q--;
  28. 		long long lid = (*q).id, lh = (*q).he;
  29. 		q++;
  30. 		q++;
  31. 		long long rid = (*q).id, rh = (*q).he;
  32. 		q--;
  33. 		if (abs(rh - h[i]) >= abs(lh - h[i])) {
  34. 			gb = lid;
  35. 			q--; q--;
  36. 			if (abs(rh - h[i]) < abs((*q).he - h[i])) {
  37. 				ga = rid;
  38. 			} else {
  39. 				ga = (*q).id;
  40. 			}
  41. 		} else {
  42. 			gb = rid;
  43. 			q++; q++;
  44. 			if (abs((*q).he - h[i]) < abs(lh - h[i])) {
  45. 				ga = (*q).id;
  46. 			} else {
  47. 				ga = lid;
  48. 			}
  49. 		}
  50. 		f[0][i][0] = ga;
  51. 		f[0][i][1] = gb;
  52. 		da[0][i][0] = abs(h[ga] - h[i]);
  53. 		db[0][i][1] = abs(h[gb] - h[i]);
  54. 	}
  55. }
  56. pair<long long, long long> w(long long s, long long x) {
  57. 	long long p = s;
  58. 	long long la = 0;
  59. 	long long lb = 0;
  60. 	for (int i = 17; i >= 0; i--) {
  61. 		if (f[i][p][0] && la + lb + da[i][p][0] + db[i][p][0] <= x) {
  62. 			la += da[i][p][0];
  63. 			lb += db[i][p][0];
  64. 			p = f[i][p][0];
  65. 		}
  66. 	}
  67. 	return {la, lb};
  68. }
  69. int main() {
  70. 	cin >> n;
  71. 	for (long long i = 1; i <= n; i++) cin >> h[i];
  72. 	cin >> x0;
  73. 	cin >> m;
  74. 	init();
  75. 	long long tt = 10;
  76. 	for (int i = 1; i <= 17; i++) {
  77. 		for (int j = 1; j <= n; j++) {
  78. 			for (int k = 0; k <= 1; k++) {
  79. 				if (i == 1) {
  80. 					f[i][j][k] = f[0][f[0][j][k]][1 - k];
  81. 					da[i][j][k] = da[0][f[0][j][k]][1 - k] + da[0][j][k];
  82. 					db[i][j][k] = db[0][f[0][j][k]][1 - k] + db[0][j][k];
  83. 				} else {
  84. 					f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
  85. 					da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];
  86. 					db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
  87. 				}
  88. 			}
  89. 		}
  90. 	}
  91. 	long double ans = 1.00 * 0x3f3f3f3f;
  92. 	long long an = 0;
  93. 	for (int i = 1; i <= n; i++) {
  94. 		pair<long long, long long> a = w(i, x0);
  95. 		long long la = a.first;
  96. 		long long lb = a.second;
  97. 		if (lb == 0) continue;
  98. 		long double d = 1.00 * la / (1.00 * lb);
  99. 		if (d < ans) {
  100. 			ans = d;
  101. 			an = i;
  102. 		} else if (d == ans) {
  103. 			if (h[an] < h[i]) an = i;
  104. 		}
  105. 	}
  106. 	cout << an << endl;
  107. 	long long a, b;
  108. 	for (int i = 1; i <= m; i++) {
  109. 		cin >> a >> b;
  110. 		pair<long long, long long> c = w(a, b);
  111. 		cout << c.first << ' ' << c.second << endl;
  112. 	}
  113. 	return 0;
  114. }

一般在设计出状态以后，发现空间复杂度不符合要求，且有状态能够随意划分，则可以使用倍增优化；

三. 数据结构优化

适用范围：

  1. 时间复杂度能够忍受 $ \Theta (n \ log \ n) $

  2. 状态转移方程中要维护 $ \max $ 或 $ \min $ 或 $ sum $ 且区间固定；

一般使用线段树或树状数组

例题

Luogu P4644 [USACO05DEC] Cleaning Shifts S

我们可以定义 $ f[i] $ 表示到第 $ i $ 个时间点时的最小花费，我们用一个结构体存储每头牛的信息（$ st $ 为开始时刻，$ ed $为结束时刻， $ w $ 为工资），显然有状态转移方程：

\[f[e[i].ed] = \min_{j \in [e[i].st - 1, e[i].ed - 1]} {f[j]} + e[i].w \]

我们发现， $ DP $ 的方向是按照 $ ed $ 的顺序从左向右走的，所以先要将结构体按 $ ed $ 的顺序排序；

时间复杂度：$ \Theta (n^2) $ 极限数据会被卡；

考虑优化；

发现状态转移方程有这一项：

\[\min_{j \in [e[i].st - 1, e[i].ed - 1]}{f[j]} \]

对于一个区间固定求最小值的操作，很容易想到用线段树维护；

具体实现方法：

  1. 初始化

\[f[m - 1] = 0 \]

  1. 使用线段树查询区间 $ [e[i].st - 1, e[i].ed] $ 的最小值并更新（注意这里要取到 $ e[i].ed $ 因为后面要插入 $ f[i] $ ，这样做继承了原来的最小值，便于后面更新）；

  2. 状态转移

\[f[e[i].ed] = \min(f[e[i].ed], ask(1, e[i].st - 1, e[i].ed) + e[i].w); \]

这里的 $ ask $ 是线段树的询问操作；

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. struct sss{
  7. 	int st, ed, w;
  8. 	bool operator <(const sss &A) const {
  9. 		return ed < A.ed;
  10. 	}
  11. }e[10000005];
  12. inline int ls(int x) {
  13. 	return x << 1;
  14. }
  15. inline int rs(int x) {
  16. 	return x << 1 | 1;
  17. }
  18. struct sas{
  19. 	int l, r, mi;
  20. }tr[90000005];
  21. int n, m, t;
  22. int f[10000005];
  23. void bt(int id, int l, int r) {
  24. 	tr[id].l = l;
  25. 	tr[id].r = r;
  26. 	if (l == r) {
  27. 		tr[id].mi = f[l];
  28. 		return;
  29. 	}
  30. 	int mid = (l + r) >> 1;
  31. 	bt(ls(id), l, mid);
  32. 	bt(rs(id), mid + 1, r);
  33. 	tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
  34. }
  35. int ask(int id, int l, int r) {
  36. 	if (r < l) return 0x3f3f3f3f;
  37. 	if (tr[id].l >= l && tr[id].r <= r) {
  38. 		return tr[id].mi;
  39. 	}
  40. 	int mid = (tr[id].l + tr[id].r) >> 1;
  41. 	if (r <= mid) return ask(ls(id), l, r);
  42. 	else if (l > mid) return ask(rs(id), l, r);
  43. 	else return min(ask(ls(id), l, mid), ask(rs(id), mid + 1, r));
  44. }
  45. void add(int id, int pos, int d) {
  46. 	if (tr[id].l == tr[id].r) {
  47. 		tr[id].mi = d;
  48. 		return;
  49. 	}
  50. 	int mid = (tr[id].l + tr[id].r) >> 1;
  51. 	if (pos <= mid) add(ls(id), pos, d);
  52. 	else add(rs(id), pos, d);
  53. 	tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
  54. }
  55. int main() {
  56. 	cin >> n >> m >> t;
  57. 	m++;
  58. 	t++;
  59. 	bool vi = false;
  60. 	for (int i = 1; i <= n; i++) {
  61. 		cin >> e[i].st >> e[i].ed >> e[i].w;
  62. 		e[i].st++;
  63. 		e[i].ed++; //将时间段转化为时间点
  64. 	}
  65. 	sort(e + 1, e + 1 + n);
  66. 	memset(f, 0x3f, sizeof(f));
  67. 	f[m - 1] = 0;
  68. 	bt(1, m - 1, t);
  69. 	for (int i = 0; i <= n; i++) {
  70. 		f[e[i].ed] = min(f[e[i].ed], ask(1, e[i].st - 1, e[i].ed) + e[i].w);
  71. 		add(1, e[i].ed, f[e[i].ed]);
  72. 	}
  73. 	if (f[t] == 0x3f3f3f3f) { //判断能不能被更新
  74. 		cout << -1;
  75. 	} else {
  76. 		cout << f[t];
  77. 	}
  78. 	return 0;
  79. }

四. 单调队列优化

类比数据结构优化，单调队列优化的特征为区间不固定（滑动窗口），队列头部在保证合法的状态下，是现在的最优决策，在尾部将每次更新的决策插入，同时维护队列的单调性；

适用范围：1D/1D动态规划

所谓1D/1D动态规划，即状态转移方程形如

\[f[i] = \min_{j \in [l(i), r(i)]} f[j] + val(i, j) \]

的动态规划;

对于纯单调队列的优化，其中 $ val(i, j) $ 的每一项仅与 $ i $ 和 $ j $ 之中的一个有关（即不能出现 $ i $ 和 $ j $ 的乘积项），这是用单调队列优化的基本条件；

单调队列优化的基本思路：

对于一个状态 $ i $，我们要做的就是在决策范围单调变化的同时，快速找出一个最优决策 $ j $，然后更新现在的状态，单调队列就是在维护这样一个合法的决策集合，使我们能够快速更新现在的状态；

依据这个思路，我们来分析一下时间复杂度：

假设现在 $ i \in [1, n] $，则：

朴素：枚举一次 $ i $ ，同时内层循环枚举 $ j \in [l(i), r(i)] $（一般是 $ j \in [0, i) $ ），时间复杂度为 $ \Theta (n^2) $；

单调队列优化：每个 $ j $ 至多进队和出队一次，时间复杂度为 $ \Theta (n) $；

例题

Luogu P2254 [NOI2005] 瑰丽华尔兹

首先很容易想出一个状态 $ f[k][i][j] $ 代表在第 $ k $ 时刻，在 $ (i, j) $ 所滑行的最长距离；

很容易想出状态转移方程：

\[\begin{equation} f[k][i][j] \begin{cases} \max(f[k][i][j], f[k - 1][i][j]) \ (所有情况)\\max(f[k][i][j], f[k - 1][i + 1][j] + 1) \ (t[k] = 1) \\max(f[k][i][j], f[k - 1][i - 1][j] + 1) \ (t[k] = 2) \\max(f[k][i][j], f[k - 1][i][j + 1] + 1) \ (t[k] = 3) \\max(f[k][i][j], f[k - 1][i][j - 1] + 1) \ (t[k] = 4) \\end{cases} \end{equation} \]

其中，$ t[k] $ 代表滑行方向；

可以用滚动数组将第一位滚掉以满足内存需求；

时间复杂度：$ \Theta (Tnm) $ 需要优化；

不妨从状态设计下手，发现时间段的范围很小，所以可以重定义状态 $ f[k][i][j] $ 代表在第 $ k $ 个时间段，在 $ (i, j) $ 所滑行的最长距离；

状态转移方程：

\[f[k][i][j] = \max(f[k - 1][i][j], \ \max(f[k][i^`][j^`] + dis((i, j) , (i^`, j^`)))) \]

发现时间复杂度 $ \Theta (kn^2 m^2) $ 需要优化；

不难发现，对于一个相同的时间段，移动的方向是固定的，且随着 $ (i, j) $ 的变化，决策的范围也在单调变化，且 $ dis $ 仅和 $ i $ 与 $ j $ 有关，所以对于 $ dis $ 可以用单调队列优化；

具体实现操作：

  1. 分情况确定移动的方向；

  2. 在此方向维护一个单调队列存相应的决策 $ j $，每次更新时首先判断队头是否越界（即 $ dis $ 是否大于时间段），如果越界，弹出队头；

  3. 队头即为最优决策，用队头更新当前状态；

  4. 将当前状态作为决策从队尾插入，同时维护单调性；

注意： 单调队列中维护的是决策（即状态转移方程中的 $ j $），每次进行第 $ 4 $ 步时需要将决策带回状态转移方程进行判断；

第一维可以用滚动数组滚掉；

具体实现请看代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <deque>
  5. #include <cmath>
  6. using namespace std;
  7. int n, m, x, y, kk;
  8. int a[505][505];
  9. int t[40005];
  10. int f[2][205][205];
  11. int T;
  12. char c;
  13. struct sss{
  14. 	int st, ed, d;
  15. }e[10000005];
  16. deque<int> q;
  17. int main() {
  18. 	cin >> n >> m >> x >> y >> kk;
  19. 	for (int i = 1; i <= n; i++) {
  20. 		for (int j = 1; j <= m; j++) {
  21. 			cin >> c;
  22. 			if (c == '.') {
  23. 				a[i][j] = 1;
  24. 			}
  25. 			if (c == 'x') {
  26. 				a[i][j] = 0;
  27. 			}
  28. 		}
  29. 	}
  30. 	for (int i = 1; i <= n; i++) {
  31. 		for (int j = 1; j <= m; j++) {
  32. 			f[0][i][j] = 0xcfcfcfcf;
  33. 		}
  34. 	}
  35. 	f[0][x][y] = 0;
  36. 	int p = 0;
  37. 	for (int i = 1; i <= kk; i++) {
  38. 		cin >> e[i].st >> e[i].ed >> e[i].d;
  39. 	}
  40. 	for (int k = 1; k <= kk; k++) {
  41. 		p ^= 1;
  42. 		for (int i = 1; i <= n; i++) {
  43. 			for (int j = 1; j <= m; j++) {
  44. 				f[p][i][j] = 0xcfcfcfcf;
  45. 			}
  46. 		}
  47. 		if (e[k].d == 3) {
  48. 			for (int i = 1; i <= n; i++) {
  49. 				q.clear(); //注意每次清空队列；
  50. 				for (int j = m; j >= 1; j--) {
  51. 					if (a[i][j] == 0) {
  52. 						q.clear(); //碰到障碍物后，前面的决策都不可取，所以要清空队列；
  53. 						continue;
  54. 					}
  55. 					while(!q.empty() && q.front() > j + (e[k].ed - e[k].st + 1)) q.pop_front();
  56. 					while(!q.empty() && f[p ^ 1][i][j] + j >= f[p ^ 1][i][q.back()] + q.back()) q.pop_back();
  57. 					q.push_back(j);
  58. 					f[p][i][j] = max(f[p][i][j], f[p ^ 1][i][q.front()] + q.front() - j);
  59. 				}
  60. 			}
  61. 		}
  62. 		else if (e[k].d == 4) {
  63. 			for (int i = 1; i <= n; i++) {
  64. 				q.clear();
  65. 				for (int j = 1; j <= m; j++) {
  66. 					if (a[i][j] == 0) {
  67. 						q.clear();
  68. 						continue;
  69. 					}
  70. 					while(!q.empty() && q.front() < j - (e[k].ed - e[k].st + 1)) q.pop_front();
  71. 					while(!q.empty() && f[p ^ 1][i][j] - j >= f[p ^ 1][i][q.back()] - q.back()) q.pop_back();
  72. 					q.push_back(j);
  73. 					f[p][i][j] = max(f[p][i][j], f[p ^ 1][i][q.front()] + j - q.front());
  74. 				}
  75. 			}
  76. 		}
  77. 		else if (e[k].d == 1) {
  78. 			for (int j = 1; j <= m; j++) {
  79. 				q.clear();
  80. 				for (int i = n; i >= 1; i--) {
  81. 					if (a[i][j] == 0) {
  82. 						q.clear();
  83. 						continue;
  84. 					}
  85. 					while(!q.empty() && q.front() > i + (e[k].ed - e[k].st + 1)) q.pop_front();
  86. 					while(!q.empty() && f[p ^ 1][i][j] + i >= f[p ^ 1][q.back()][j] + q.back()) q.pop_back();
  87. 					q.push_back(i);
  88. 					f[p][i][j] = max(f[p][i][j], f[p ^ 1][q.front()][j] + q.front() - i);
  89. 				}
  90. 			}
  91. 		}
  92. 		else if (e[k].d == 2) {
  93. 			for (int j = 1; j <= m; j++) {
  94. 				q.clear();
  95. 				for (int i = 1; i <= n; i++) {
  96. 					if (a[i][j] == 0) {
  97. 						q.clear();
  98. 						continue;
  99. 					}
  100. 					while(!q.empty() && q.front() < i - (e[k].ed - e[k].st + 1)) q.pop_front();
  101. 					while(!q.empty() && f[p ^ 1][i][j] - i >= f[p ^ 1][q.back()][j] - q.back()) q.pop_back();
  102. 					q.push_back(i);
  103. 					f[p][i][j] = max(f[p][i][j], f[p ^ 1][q.front()][j] - q.front() + i);
  104. 				}
  105. 			}
  106. 		}
  107. 	}
  108. 	int ans = 0;
  109. 	for (int i = 1; i <= n; i++) {
  110. 		for (int j = 1; j <= m; j++) {
  111. 			ans = max(ans, f[p][i][j]);
  112. 		}
  113. 	}
  114. 	cout << ans;
  115. 	return 0;
  116. }

不难发现，在单调队列优化时，我们通常将状态看做常量，将决策看做变量，每次保证决策的单调性，是做这部分题的小技巧；

推荐一道题

Luogu P2569 [SCOI2010] 股票交易

五. 斜率优化

刚刚我们探讨了单调队列优化的基本操作，让我们回顾一下1D/1D动态规划的状态转移方程：

\[f[i] = \min_{j \in [l(i), r(i)]} f[j] + val(i, j) \]

我们知道，当$ val(i, j) $ 的每一项仅与 $ i $ 和 $ j $ 之中的一个有关（即不能出现 $ i $ 和 $ j $ 的乘积项）时，可以用单调队列优化；

如果有乘积项，就需要用到斜率优化；

当出现乘积项时，我们很容易联想到平面直角坐标系中形如 $ y = kx + b $ 的一次函数，依据这个思想，我们来探讨斜率优化；

斜率优化的主要思想：及时排除无用决策；

接下来，我们依据例题来解释斜率优化；

例题

Luogu P5785 [SDOI2012] 任务安排

首先求出 $ T $， $ C $ 的前缀和 $ sumt $ 和 $ sumc $ ；

定义$ f[i][j] $ 表示前 $ i $ 个任务分成 $ j $ 批施行的最小费用，很容易得出状态转移方程：

\[f[i][j] = \min_{k \in [0, i)} f[k, j - 1] + (S * j + sumt[i]) * (sumc[i] - sumc[k]) \]

时间复杂度：$ \Theta (n^3) $

考虑优化；

不妨设题目中 $ t $ 都为正整数；

不难发现，状态的第二维（批次）是一个附加状态，即它不是求答案的直接手段，只是求答案的一个附加手段；

考虑优化掉这一维；

其实当我们在执行一批任务时，并不是关心它之前机器启动了多少次，而是应该关心机器的启动对现在状态所耽误的时间；

如果不知道之前机器启动了多少次，怎么去求机器的启动对现在状态所耽误的时间？

我们可以换一个角度思考，机器因执行一批任务所花费的启动时间 $ S $ 会累加到后续所有任务完成的时间之中，对此，我们引入一个思想，叫做费用提前计算，也就是说，当每启动一次机器时，就把它对之后的所有影响（一直到 $ n $）全部计算在内，这样就达到了求出最小费用的优化；

依据上述思路，我们定义 $ f[i] $ 表示把前 $ i $ 个任务分成若干批执行的最小费用，有状态转移方程：

\[f[i] = \min_{j \in [0, i)} f[j] + sumt[i] * (sumc[i] - sumc[j]) + S * (sumc[n] - sumc[j]) \]

值得注意的是，在费用提前计算的思想下，只有目标 $ f[n] $ 是正确的，其它结果（例如 $ f[n - 1] $）是偏大的；

时间复杂度：$ \Theta (n^2) $

还是不行，再次考虑优化；

发现这个优化过的状态转移方程满足1D/1D的动态规划，且 $ val $ 项有乘积项，考虑斜率优化；

将方程展开，得到：

\[f[i] = \min_{j \in [0, i)} f[j] - (S + sumt[i]) * sumc[j] + sumt[i] * sumc[i] + S * sumc[n] \]

因为在平面直角坐标系中，纵坐标是随横坐标变化的，所以我们去掉 $ \min $，将只含 $ j $ 的项移到等式左面，剩下的项移到等式右面，可得：

\[f[j] = (S + sumt[i]) * sumc[j] + f[i] - sumt[i] * sumc[i] - S * sumc[n] \]

在以 $ sumc[j] $ 为横坐标，$ f[j] $ 为纵坐标的平面直角坐标系中，这是一条以 $ S + sumt[i] $ 为斜率，$ f[i] - sumt[i] * sumc[i] - S * sumc[n] $ 为截距的直线；

这也就是说，我们的决策其实也就对应这个平面直角坐标系中的一个个点，这条直线就对应着我们现在的状态，要用决策去更新状态，需要让这条线去撞决策点；

image

如图所示；

现在我们想要让 $ f[i] $ 最小，观察得截距中其它项都是常数，那么我们让截距最小，所经过的点即为最优决策；

现在我们来考虑一个点能成为最优决策的条件，并依此排除无用决策；

image

如图，发现当这三个点构成一个“上凸”形时，点 $ 2 $ 不可能成为最优决策；

image

如图，发现当这三个点构成一个“下凸”形时，这三个点都可能成为最优决策；

发现：一个决策点 $ 2 $ 能够成为最优决策，当且仅当：

\[\frac{f[j_2] - f[j_1]}{sumc[j_2] - sumc[j_1]} < \frac{f[j_3] - f[j_2]}{sumc[j_3] - sumc[j_2]} \]

这里有个技巧，当我们求斜率时，最好保证两边都为正数，以省去不必要的计算与变号

当取等号时， \(j_2\) 与 \(j_3\) 同时成为最优决策；

于是，我们只需用单调队列维护一个下凸壳（如第二张图）即可，其中斜率单调递增；

当我们找最优决策时，可以发现最优决策点与左边点的连线斜率比 $ S + sumt[i] $ 小，右边比它大；

所以，总的操作为：

  1. 检查队首斜率与直线斜率 $ S + sumt[i] $ 的关系，若前者小于等于后者，根据斜率 $ S + sumt[i] $ 的单调递增性，需使队首出队；

  2. 此时，队首即为最优决策，更新现在的状态；

  3. 依据 $ sumc[j] $ 的单调递增性，我们从队尾将已经更新的状态作为一个新的决策插入，同时维护决策斜率的单调递增性；

在进行第三步时，我们将 $ i $ 与队尾建立联系，求出斜率，同时将此斜率与队尾斜率进行比较，以维护斜率的单调递增性；

时间复杂度优化到了 $ \Theta (n) $；

到这，实现的代码为：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. int n, s;
  6. int t[1000005], c[1000005];
  7. int f[1000005];
  8. int sumt[1000005], sumc[1000005];
  9. int main() {
  10. 	cin >> n >> s;
  11. 	for (int i = 1; i <= n; i++) cin >> t[i] >> c[i];
  12. 	sumt[1] = t[1];
  13. 	sumc[1] = c[1];
  14. 	for (int i = 1; i <= n; i++) {
  15. 		sumt[i] = sumt[i - 1] + t[i];
  16. 		sumc[i] = sumc[i - 1] + c[i];
  17. 	}
  18. 	memset(f, 0x3f, sizeof(f));
  19. 	f[0] = 0;
  20. 	for (int i = 1; i <= n; i++) {
  21. 		for (int j = 0; j < i; j++) {
  22. 			f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
  23. 		}
  24. 	}
  25. 	cout << f[n];
  26. 	return 0;
  27. }

但我们讨论的都是 $ t $ 都为正整数的情况，如果不是呢（即 $ sumt $ 并不是单调递增的）？

很显然，我们上述过程中的第一步就不对了，那也没有关系，此时问题是队首不一定是最优决策，所以我们不能弹出队首，而必须维护整个凸壳，依据决策斜率的单调性，每次二分查找满足上述过程中的第一步并更新即可；

队尾操作不变；

时间复杂度：$ \Theta (n \ log \ n) $，可以通过本题；

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. #define int long long
  6. int n, s;
  7. int t[1000005], c[1000005];
  8. int f[1000005];
  9. int sumt[1000005], sumc[1000005];
  10. int q[10000005];
  11. int l, r;
  12. int bi(int k) {
  13. 	if (l == r) return q[l];
  14. 	int L = l, R = r;
  15. 	while(L <= R) {
  16. 		int mid = (L + R) >> 1;
  17. 		if (f[q[mid + 1]] - f[q[mid]] <= k * (sumc[q[mid + 1]] - sumc[q[mid]])) L = mid + 1;
  18. 		else R = mid - 1;
  19. 	}
  20. 	return q[L];
  21. }
  22. main() {
  23. 	cin >> n >> s;
  24. 	for (int i = 1; i <= n; i++) cin >> t[i] >> c[i];
  25. 	sumt[1] = t[1];
  26. 	sumc[1] = c[1];
  27. 	for (int i = 1; i <= n; i++) {
  28. 		sumt[i] = sumt[i - 1] + t[i];
  29. 		sumc[i] = sumc[i - 1] + c[i];
  30. 	}
  31. 	memset(f, 0x3f, sizeof(f));
  32. 	f[0] = 0;
  33. 	l = 0, r = 0;
  34. 	q[0] = 0;
  35. 	for (int i = 1; i <= n; i++) {
  36. 		int j = bi(s + sumt[i]);
  37. 		f[i] = min(f[i], f[j] - (s + sumt[i]) * sumc[j] + sumt[i] * sumc[i] + s * sumc[n]);
  38. 		while(l < r && (f[q[r]] - f[q[r - 1]]) * (sumc[i] - sumc[q[r]]) >= (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - 1]])) r--;
  39. 		q[++r] = i;
  40. 	}
  41. 	cout << f[n];
  42. 	return 0;
  43. }

推荐题目

Luogu CF311B Cats Transport

斜率优化一般会结合前缀和，在求解斜率时，可以化除为乘，但不易查错。也可以将斜率写为函数，但容易丢精度；

六. 四边形不等式优化

四边形不等式定义：

\[w(a, d) + w(b, c) \geq w(a, c) + w(b, d) \ (a \leq b \leq c \leq d) \]

其中 $ w(a, b) $ 表示定义在整数集合上的二元函数；

定理

对于形如

\[f[i] = \min_{j \in [0, i)} f[j] + val(i, j) \]

的状态转移方程，设 $ p[i] $ 是 $ f[i] $ 的最优决策，若 $ p $ 在定义域内单调不减，则称 $ f $ 具有决策单调性；

在状态转移方程

\[f[i] = \min_{j \in [0, i)} f[j] + val(i, j) \]

中，若函数 $ val $ 满足四边形不等式，则称 $ f $ 具有决策单调性；

显然，在 $ p $ 数组中，决策是连续的，如图：

image

这显示了 $ p $ 数组中存储的决策；

维护一个三元组 $ j, l, r $， $ j $ 代表当前段内的决策，$ l $ $ r $ 分别代表当前决策的左右区间（管辖范围）；

用单调队列维护 $ p $ 数组，可以概括为以下几个步骤：

  1. 检查队头，设队头三元组为 $ j, l, r $，若 $ r < i $，弹出队头；

设队尾三元组为 $ j_0, l_0, r_0 $，则：

  1. 若对于 $ f[l_0] $ 来说，$ i $ 比 $ j_0 $ 更优，则删除队尾；

  2. 否则，在队尾二分查找，找到一个位置，使得在这个位置及右边 $ i $ 比 $ j_0 $ 更优，左边$ j_0 $ 比 $ i $ 更优，这个位置记为 $ pos $；

  3. 将三元组 $ i, pos, n $ 插入队尾；

结语

概括来讲，$ DP $ 优化思路为：

  1. 有可随意划分的，用倍增优化；

  2. 发现环形，破环成链，或者复制一倍在末尾，用环形处理的思路；

  3. 状态转移的方向与 $ DP $ 方向不一，用后效性处理的思路；

  4. 状态转移方程需要在定区间内查询最值等等，用数据结构优化；

  5. 1D/1D的动态规划，需要维护动态区间，当 $ val $ 中有乘积项时，用斜率优化。没有时用单调队列优化；

  6. 当 $ val $ 满足四边形不等式时，依据决策的单调性优化；

总之， $ DP $ 优化因题而异，做好优化需要我们快速且正确的设计出状态转移方程，打好基础，才能做到掌握优化；

原文链接：https://www.cnblogs.com/PeppaEvenPig/p/18244558

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号