引言斜率优化是一种用于优化特定形式动态规划DP的数学技巧。当 DP 转移方程可以写成dp[i] min/max{ dp[j] A(i) * B(j) C(i) D(j) }且其中A(i) * B(j)是乘积项时直接枚举 j 的复杂度为 O(n²)无法满足大数据范围。斜率优化通过将转移决策点视为平面上的点利用凸包Convex Hull和单调队列将转移复杂度降至 O(n) 或 O(n log n)。前置知识线性DP能够写出状态转移方程且转移仅依赖之前的状态。单调队列维护一个队列其中元素单调递增/递减用于滑动窗口最值问题。凸包与斜率平面上的点 (x, y)两点间斜率 k (y₂ - y₁) / (x₂ - x₁)。下凸包Convex Hull的相邻点斜率递增上凸包的斜率递减。一次函数形如 y kx b其中 k 是斜率b 是截距。核心思想考虑如下的 DP 转移方程以最小化为例textdp[i] min{ dp[j] (a[i] - b[j])² } (j i)展开后得到dp[i] min{ dp[j] a[i]² - 2 a[i] b[j] b[j]² } a[i]² min{ (dp[j] b[j]²) - 2 a[i] b[j] }令X(j) b[j]Y(j) dp[j] b[j]²k 2 a[i]与 i 有关则转移变为dp[i] a[i]² min{ Y(j) - k * X(j) }。注意Y(j) - k * X(j)是直线y kx b在 x X(j) 处的纵坐标与目标值的差更直接地我们将每个决策 j 视为平面上的点(X(j), Y(j))要最小化Y(j) - k X(j)。对于固定的 k我们想要Y(j) - k X(j)最小即在过点 (X(j), Y(j)) 且斜率为 k 的直线中使得截距 b Y(j) - k X(j) 最小。这等价于用一条斜率为 k 的直线从下方去“触碰”这些点集最先碰到的点就是最优决策。如果这些点构成下凸包随着 k 单调递增最优决策点也在凸包上单调右移。因此可以维护一个单调队列存储凸包上的点并用队首作为当前最优转移。斜率优化的推导步骤标准流程写出原始转移方程并尝试整理成dp[i] min{ dp[j] A(i) * B(j) C(i) D(j) }其中 A(i), B(j) 是只与 i 或 j 有关的项C(i), D(j) 是常数项。分离与 i 和 j 相关的项得到形如dp[i] C(i) min{ (dp[j] D(j)) - (-A(i)) * B(j) }令X(j) B(j)Y(j) dp[j] D(j)k(i) -A(i)则min{ Y(j) - k(i) * X(j) }是核心。考虑两个决策 j 和 k (j k)若 j 优于 k则Y(j) - k(i) X(j) Y(k) - k(i) X(k) - Y(j) - Y(k) k(i) (X(j) - X(k))假设 X 单调通常 B(j) 随 j 单调分情况讨论若 X(j) X(k) 且斜率比较(Y(j)-Y(k))/(X(j)-X(k)) k(i)则 j 优于 k对于最小化问题维护下凸包。维护凸包横坐标 X 单调递增 → 可使用单调队列维护下凸包斜率单调递增。斜率 k(i) 单调递增 → 队首可直接弹出旧决策。若 k(i) 不单调则需在凸包上二分查找最优位置。具体实现模板最小值X 递增k 递增int l 1, r 1; q[1] 0; // 初始决策 0 for (int i 1; i n; i) { // 弹出队首当队首与次队首的斜率 k(i) 时队首劣 while (l r slope(q[l], q[l1]) k(i)) l; int j q[l]; dp[i] C(i) (Y(j) - k(i) * X(j)); // 插入当前决策 i维护下凸包 while (l r slope(q[r-1], q[r]) slope(q[r], i)) --r; q[r] i; }实现细节与注意事项横坐标相等若 X(j) X(k)则需保留 Y 较小的那个对于最小化问题否则除以零。斜率比较时使用交叉相乘避免浮点误差(Y2-Y1)*(X3-X2) (Y3-Y2)*(X2-X1)等效于斜率比较。初始状态通常将决策 0或一个虚拟起点加入队列。数据类型斜率优化常涉及大整数建议使用long long或__int128。性质决策单调性若 k(i) 单调则最优决策点 j 也是单调不减的。凸包维护的单调性对于最小值问题维护下凸包对于最大值问题维护上凸包。复杂度若 k(i) 和 X(j) 均单调总复杂度 O(n)否则为 O(n log n)。例题例题1玩具装箱Luogu P3195 / HNOI2008题意有 n 个玩具长度 c[i]。将玩具分成若干组每组从 i 到 j 的费用为(j-i sum(c[i..j]) - L)²求最小总费用。DP 方程dp[i] min{ dp[j] (sum[i] - sum[j] i - j - 1 - L)² } (0 ≤ j i)令a[i] sum[i] ib[j] sum[j] j 1 L则dp[i] min{ dp[j] (a[i] - b[j])² } a[i]² min{ (dp[j] b[j]²) - 2 a[i] b[j] }令X(j) b[j]Y(j) dp[j] b[j]²k(i) 2 a[i]斜率优化求解。例题2任务安排Luogu P2365 / P5785题意n 个任务每个任务有耗时 t[i] 和费用系数 c[i]。分组每组启动时间 S任务费用 完成时刻 × 费用系数。求最小总费用。DP 方程dp[i] min{ dp[j] (sumC[i] - sumC[j]) * sumT[i] S * (sumC[n] - sumC[j]) }整理后得到斜率优化形式注意横坐标sumC[j]单调递增但斜率sumT[i]也递增P2365或不一定递增P5785需二分查找。例题3土地购买Luogu P2900 / USACO08MAR题意n 块土地每块有长宽。可以分组购买费用 组内最大长 × 最大宽。求最小总费用。预处理先按长排序去掉被其他土地完全包含的土地长和宽均小。然后宽单调递减或递增DP 方程为dp[i] min{ dp[j] w[j1] * h[i] }其中 h[i] 单调递增w[j1] 单调递减。这是一个斜率优化模型注意横坐标-w[j1]的单调性。