决策单调性：A ~ F, I
基础知识
考虑最简单情形：\(f_i = \min\limits_{k = 0}^{i - 1} w(k, i)\)。
一般这种问题需要 \(O(n ^ 2)\) 的时间，但如果满足决策单调性，就可以在 \(O(n \log n)\) 的时间完成。
决策单调性：设 \(i\) 的决策点为 \(opt_{i}\)，有 \(opt_{i - 1} \le opt_i \le opt_{i + 1}\)。
原理
最常见的证明方式为四边形不等式。
若对于任意 \(a < b < c < d\)，有 \(w(a, c) + w(b, d) \le w(a, d) + w(b, c)\)（交叉小于包含），则 \(w\) 满足四边形不等式。当然，如果题目要求的是最大值，符号就需要倒过来。
如果 \(w\) 满足四边形不等式，则问题有决策点调性。
反证法：
若 \(opt(d) = a < opt(c) = b\)，根据条件有 \(w(a, d) \le w(b, d)， w(b, c) < w(a, c)\)。
则 \(w(a, d) + w(b, c) < w(b, d) + w(a, c)\)，与四边形不等式矛盾。
注意：有些问题具有决策单调性，但不满足四边形不等式。
实现
首先申明一下，一个问题具有决策单调性，不代表每个决策点的答案是单调的，即有 1 2 3 5 4 0 之类的情况。也就不能使用双指针之类的方式求出决策点。
下面介绍两种实现方式：分治、二分队列。时间复杂度均为 \(O(n \log n)\)。
一般情况下，使用分治足够了，这种方法好写且常数小。但是有些情况是不能使用分治的，见例题 3。
分治
我们实现一个 solve(l, r, pl, pr) 函数，表示区间 \(l, r\) 的决策点在 \([pl, pr]\)。
求出区间的中点 \(mid\)，枚举 \([pl, pr]\) 内的点，尝试转移到 \(mid\)，求出 \(opt_{mid}\)。
根据决策单调性，\(opt_{l} \le \dots \le opt_{mid - 1} \le opt_mid \le opt_{mid + 1} \le \dots \le opt_r\)。所以递归实现 solve(l, mid - 1, pl, opt[mid]) 与 solve(mid + 1, r, opt[mid], pr) 即可。
时间复杂度：因为每次取的是中点 \(mid\)，所以分治最多 \(O(\log n)\) 层，而每层的 \(pr - pl + 1\) 之和都是 \(O(n)\) 的，总时间复杂度：\(O(n \log n)\)。
二分队列
其实这种方法才是传统的方法，它更万能。但是分治实在太好写了。
由决策单调性，对于每个决策点 \(j\)，能使它成为最优决策点的 \(i\) 一定是一段区间，我们称 \(j\) 对应这个区间。于是我们可以维护一个队列，里面存所有可能成为最优决策点的 \(j\), 以及它们对应的区间 \([l_j, r_j]\)。
依次枚举每个 \(i = 1, 2, 3 \dots n\)，现在求 \(f_i\)。进行一下两步：
- 若当前队首对应的 \(l < i\)，则
l++。 - 若队首的 \(l > r\)，即队首已不可能成为最优决策点。弹掉队首。
现在的队首就是 \(i\) 的最优决策点，转移即可。求出 \(f_i\) 后，暂时令 \(l_i = n + 1, r_i = n\)。不断尝试弹出队尾的元素（下面设现在队尾的元素为 \(u\)）
-
若队列为空，那么 \(i\) 暂时成为所有位置的最优决策点，令 \(l_i = 1\)，退出。
-
如果对于 \(l_u\) ，\(i\) 比 \(u\) 更 \(u\)，那么 \(l_i \le l_u\)。所以 \(u\) 不可能成为最优决策点了，弹掉它。继续尝试弹队尾元素。
-
否则 \(l_i > l_u\)，所以 \(l_i \in (l_u, r_u + 1]\)，进行二分求出 \(l_i\) 并将 \(r_u\) 更新为 \(l_i - 1\)。
时间复杂度：对于每个元素至多入队一次，出队一次。因为出队是 \(O(1)\) 的，入队最多是 \(O(\log n)\)。总时间复杂度：\(O(n \log n)\)。
实现上，可以不记录 \(r_i\)，因为 \(i\) 在队列中的下一个 \(j\) 有 \(l_j = r_i + 1\)，那么 \(r_i = l_j + 1\)。
如何发现
第一种方法是证明四边形不等式，但是这个比较耗时，且有时比较复杂（非想证建议利用一些图像的性质）。所以后面的题不怎么证明。
另一种就是猜！也就是靠经验，当你不知如何优化时，猜他有决策单调性（其实可能是 wqs 二分）。然后尝试写暴力打表验证一下。
例题
CF321E
令 \(dp_{i, j}\) 表示前 \(i\) 个人用 \(j\) 个吊舱陌生度最小值。那么有 \(dp_{i, j} = \min\limits_{k = 0}^{i - 1} dp_{k, j - 1} + w(k, i)\)。其中 \(w(k, i)\) 表示第 \(k + 1 \sim i\) 个人做到同一个吊舱的代价（可以通过前缀和预先处理出来）。
对于四边形不等式的证明：\(w(a, d) + w(b, c)\) 比 \(w(a, c) + w(b, d)\) 多了两个部分（如下图），因为所有陌生度均为非负整数，所以 \(w(a, c) + w(b, d) \le w(b, c) + w(a, d)\)。即使有 \(dp_{k, j - 1}\)，也不影响，两边同时加上了 \(dp_{a, j - 1} + dp_{b, j - 1}\)。
时间复杂度：\(O(kn \log n)\)。（使用分治即可。）
#include <bits/stdc++.h>using namespace std;const int MAXN = 4003, INF = 1e9;int n, k, a[MAXN][MAXN], b[MAXN][MAXN], f[MAXN], g[MAXN];void solve(int l, int r, int pl, int pr) {if (l > r) return ;int mid = (l + r) >> 1, opt = pl;int tl = min(mid - 1, pr);for (int i = pl; i <= tl; i++) { // 求 opt[mid]if (g[i] + b[i + 1][mid] < f[mid]) {f[mid] = g[i] + b[i + 1][mid], opt = i;}}solve(l, mid - 1, pl, opt); // 分治solve(mid + 1, r, opt, pr);
}inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();return x * f;
}int main() {//ios::sync_with_stdio(0), cin.tie(0);//cin >> n >> k;n = read(), k = read(); // 此题卡常for (int i = 1; i <= n; i++) {f[i] = g[i] = INF;for (int j = 1; j <= n; j++) {a[i][j] = read(), a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];}}for (int i = 1; i <= n; i++) { // 求 w(i, j)for (int j = i; j <= n; j++) {b[i][j] = (a[j][j] - a[i - 1][j] - a[j][i - 1] + a[i - 1][i - 1]) / 2;}}for (int i = 1; i <= k; i++) {solve(1, n, 0, n);for (int j = 1; j <= n; j++) {g[j] = f[j], f[j] = INF;}}cout << g[n];return 0;
}
CF834D
同样的状态设计，令 \(dp_{i, j}\) 表示前 \(i\) 个数分成 \(j\) 段的最小代价。转移一样的。
唯一值得提的是这个 \(w(i, j)\) 的求法，虽然可以使用主席树/可持久化 01trie，但是多了一个 \(\log n\)，不够优秀。这时我们可以联想到莫队，加一个数和删一个数都是可以 \(O(1)\) 计算的。我们可以将 \(l, r, pl, pr\) 看成 \(4\) 个指针移动，移动的过程中维护答案即可（细节看代码）。
时间复杂度：\(O(nk \log n)\)。
#include <bits/stdc++.h>using namespace std;const int MAXN = 3.5e4 + 3;int n, k, sum, a[MAXN], c[MAXN], f[MAXN], g[MAXN];void add(int u) {sum += (!c[u]), c[u]++;
}void del(int u) {c[u]--, sum -= (!c[u]);
}void Move(int &L, int &R, int ql, int qr) { // 移动指针while (R < qr) R++, add(a[R]);while (L > ql) L--, add(a[L]);while (R > qr) del(a[R]), R--;while (L < ql) del(a[L]), L++;
}void solve(int l, int r, int pl, int pr) { // 维护 [pl, l] 的答案。if (l > r) return ;int mid = (l + r) >> 1, qmid = min(mid - 1, pr);int L = pl, R = l, opt = pl;f[mid] = 0, Move(L, R, pl, mid); // [pl, mid]for (int i = pl; i <= qmid; i++) {del(a[L]), L++; // [i + 1, mid]if (g[i] + sum > f[mid]) {f[mid] = g[i] + sum, opt = i;}}// 先处理右半边再处理左半边常数更小Move(L, R, opt, mid + 1);solve(mid + 1, r, opt, pr);Move(L, R, pl, l), solve(l, mid - 1, pl, opt);//Move(L, R, pl, l);
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];}c[a[1]] = 1, sum = 1;for (int i = 1; i <= k; i++) {solve(1, n, 0, n);for (int x = 1; x <= n; x++) {g[x] = f[x];}}cout << g[n];return 0;
}
洛谷 P1912
题目大意：给定长度为 \(n\) 的序列，以及 \(L, p\)。将 \(n\) 个数分成若干个区间，区间的代价为 \((s - L)^p\)，\(s\) 为区间内数之和，求最小代价。
还是 DP，令 \(dp_i\) 表示前 \(i\) 个数需要花费的最小代价，\(dp_i = \min\limits_{j = 0}^{i - 1} dp_j + w(j, i)\)。
这时候突然发现不能分治了！！！因为 \(dp_i\) 与 \(dp_j\) 之间有了依赖关系，要求 \(dp_i\) 先得求 \(dp_j\)。这就是分治这种做法的缺点：当转移有依赖关系时无法使用，就只能使用既难写常数又大的队列了（还有一种做法是 CDQ 分治，虽然两个分治常数都不大，但多了个 \(log\)）。
还有一个细节，当 \(dp_i > INF\) 时，不要对 \(INF\) 取 min，会形象决策单调性，应该使用 long double 存。
#include <bits/stdc++.h>
#define fi first
#define sc secondusing namespace std;
using ll = long long;
using lb = long double;const int MAXN = 1e5 + 3;
const ll INF = ll(1e18);string a[MAXN];
lb dp[MAXN];
pair<int, int> q[MAXN]; // 决策点，左端点
int T, n, L, p, b[MAXN], h, t, opt[MAXN];lb getw(int l, int r) {//if (dp[l] >= INF) return INF; // 不注释这句话是错误的lb ret = 1;int x = abs(b[r] - b[l] - L - 1);for (int i = p; i--; ret *= x);return ret + dp[l];
}void out(int u) { // 输出方案if (!u) return ;out(opt[u]);for (int i = opt[u] + 1; i < u; i++) {cout << a[i] << ' ';}cout << a[u] << '\n';
}void Solve() {cin >> n >> L >> p, h = t = 1, q[1] = {0, 0};for (int i = 1; i <= n; i++) {cin >> a[i], b[i] = b[i - 1] + a[i].size() + 1;}for (int i = 1; i <= n; i++) {q[h].sc += (q[h].sc < i);h += (h + 1 <= t && q[h].sc >= q[h + 1].sc);opt[i] = q[h].fi, dp[i] = getw(q[h].fi, i);int k = n + 1; // i 对应的 l[i]for (; t >= h; k = q[t].sc, t--) {if (i + 1 > q[t].sc || getw(q[t].fi, q[t].sc) < getw(i, q[t].sc)) {int l = max(i + 1, q[t].sc), r = k;while (l < r) { // 二分int mid = (l + r) >> 1;getw(q[t].fi, mid) >= getw(i, mid) ? r = mid : l = mid + 1;}k = l; break;}}if (k <= n) q[++t] = {i, k};}if (dp[n] > INF) {cout << "Too hard to arrange\n";} else {cout << ll(dp[n]) << '\n', out(n);}
}int main() {ios::sync_with_stdio(0), cin.tie(0);for (cin >> T; T--; ) {Solve(), cout << "--------------------\n";}return 0;
}洛谷 P3515
将条件变一下型 \(p \ge h_j + \sqrt{|i - j|} - h_i\)，即对于每个 \(i\) 求 \(\max \{h_j + \sqrt{|i - j|}\}\)。
先考虑 \(j < i\) 然后反过来再做一遍即可。而且根据根号函数上凸的性质可以证明四边形不等式。但是，如果在根号外面套一个上取整函数就不满足了，很神奇吧。
所以决策单调性也可以解决非 DP 的问题，且具有决策单调性的题不一定都满足四边形不等式.
时间复杂度仍是分治的 \(O(n \log n)\)。
abc 348G
可以先按 \(b_i\) 从小到大排序，枚举 \(\max_{b_i}\)，那么对于 \(k\)，\(w(k, i)\) 就是 \(a\) 数组中的前 \(i - 1\) 个数中前 \(k - 1\) 个大的之和。虽然你可以用莫队的方式，两个 set 维护。但是这个题显然是不如直接上主席树优雅的。
来看一下这个题的四边形不等式：\(w(b, d) - w(b, c) \le w(a, d) - w(a, c)\)，也就是选的的数少，新增的收益多。
时间复杂度：\(O(k \log^2 n)\)。