创建时间：2025-03-20
斜率优化DP（Convex Hull Optimisation Dynamic Programming），一种运用了DP、前缀和、不等式推导和数形结合的算法，以HDU3507为例：
题目给定了一个长度为 \(n\) 的非负整数序列 \(c\) 和非负数 \(m\)，将序列划分成 \(k\) 段，第 \(i\) 段的结尾为 \(p_i\)，使得费用
最小，输出上式的最小值。
很容易想到 \(dp_i\) 表示处理完前 \(i\) 项且最后一行的最后一项为 \(i\) 的最小费用，并通过 \(dp_i = \min\{dp_j + (\sum_{k=j+1}^i c_k)^2+m\}(j < i)\) 转移，这样时间复杂度为 \(O(n^3)\)，又可以很快地想到通过前缀和 \(s_i = \sum_{k=1}^{i} c_k\) 优化使状态转移方程变为 \(dp_i=\min\{dp_j+(s_i-s_j)^2+m\}\)，此时的复杂度为 \(O(n^2)\)。
这是最优解吗？并不是。
不妨设有 \(k<j<i\) 且 \(j\) 不比 \(k\) 更劣，即 \(dp_j+(s_i-s_j)^2+m \le dp_k+(s_i-s_k)^2+m\)，所以 \(dp_j+s_i^2-2s_i \cdot s_j+s_j^2+m \le dp_k+s_i^2-2s_i \cdot s_j+s_j^2+m\) 两边同时消去 \(s_i^2+m\) 得：\(dp_j-2s_i \cdot s_j+s_j^2 \le dp_k-2s_i \cdot s_j+s_j^2\)，所以 \((dp_j+s_j^2)-(dp_k+s_k^2) \le 2s_i(s_j-s_k)\)。显然，\(s\) 单调不减，即 \(s_j-s_k \ge 0\) 所以 \(\frac{(dp_j+s_j^2)-(dp_k+s_k^2)}{s_j-s_k} \le 2s_i\)。令 \(K(j, k) = \frac{(dp_j+s_j^2)-(dp_k+s_k^2)}{s_j-s_k}\)，故 \(K(j,k) \le 2s_i\)，不妨将 \(s_t\) 视为 \(x\)，\(dp_t+s_t^2\) 视为 \(y\)，则 \(K(j,k)\) 是点 \((dp_k+s_k^2,s_k)\) 到点 \((dp_j+s_j^2,s_j)\) 的斜率！
因为 \(j\) 不比 \(k\) 劣，且之后的斜率 \(2s_i\) 只会越来越大，所以可以将 \(k\) 踢出具有向后转移的可能性的集 \(S\)。显然， \(S\) 中的两个数 \(j\) 和 \(k\) （\(j<k\)）一定都不满足 \(K(j,k) \le 2s_i\)，否则，\(k\) 不应在 \(S\) 中。故 \(x=s_t\)，\(y=dp_t+s_t^2 (t \in S)\) 的图像的斜率应该越来越大，即构成了一个下凸壳，如下图（其中，黑线为图像，红线为斜率为 \(2s_i\) 的直线，图像外的点被移出 \(S\)）。
设此时 \(S\) 中的第一个元素为 \(j\)，由前文知：没有 \(t \in S,t>j\) 使 \(t\)、\(j\) 满足 \(K(t, j) \le 2s_i\) 式，即没有 \(j\) 不比 \(k\) 劣，换句话说，\(k\) 比任何 \(j\) 都优，所以有 \(dp_i=dp_j+(s_i-s_j)^2+m\)。
可以想到用一个手写队列来维护 \(S\)，其中 \(q[l]\) 为队首，\(q[r]\) 为队尾，\(\forall k,q[k]<q[k+1]\)。每当遍历到新的 \(i\) 时，先循环检查 \(l<r\)（显然，\(S\)中有剩余元素才有斜率）且 \(K(q[l+1],q[l]) \le 2s_i\) 直至其不成立，成立时，\(q[l]\) 不应保留在 \(S\) 中，将队首弹出，即 \(l\) ++；当求完 \(dp_i\) 将 \(i\) 加进队列前，循环检查 \(l<r\) 且 \(K(i,q[r]) \le K(q[r], q[r-1])\) 直至其不成立，若成立，则 \(q[r]\) 不应保留在 \(S\) 中（否则图像不为一个下凸壳）， 将队尾弹出，即 \(r\) --。此时便可以将 \(i\) 添加到队尾，即 \(q[\)++\(r]=i\)。
最后，只要输出 \(dp_n\) 即可，具体实现如下：
#include <bits/stdc++.h>using namespace std;#define int long longconst int MAX_N = 500050;int n, m, s[MAX_N];
int q[MAX_N], dp[MAX_N];inline int top(int x, int y) {return (dp[x] + s[x] * s[x]) - (dp[y] + s[y] * s[y]);
}
inline int down(int x, int y) {return s[x] - s[y];
}signed main() {while (cin >> n >> m) {for (int i = 1; i <= n; i++) {cin >> s[i];s[i] += s[i - 1];}int l = 1, r = 0;q[++r] = 0;for (int i = 1; i <= n; i++) {while (l < r && top(q[l + 1], q[l]) <= 2 * s[i] * down(q[l + 1], q[l]))l++;int j = q[l];dp[i] = dp[j] + (s[i] - s[j]) * (s[i] - s[j]) + m;while (l < r && top(i, q[r]) * down(q[r], q[r - 1]) <= top(q[r], q[r - 1]) * down(i, q[r]))r--;q[++r] = i;}cout << dp[n] << '\n';}return 0;
}
下面是斜率优化DP的一些其他应用：
洛谷P3195（模版变形）；
洛谷P2900（构造单调性）；
洛谷P2365（拆贡献计算）；
洛谷P3628（上凸壳处理）；
洛谷P3648（模型构造+二维DP+方案输出）；
洛谷P4360（上凸壳处理）；
洛谷P2120（P4360加强版+虚拟元素）；
洛谷P4072（二维DP）。