1. 从“暴力”到“优雅”斜率优化的核心动机如果你刷过一些动态规划的题目尤其是那些状态转移方程里带着(i - j) * (i - j)或者(a[i] - b[j])^2这类项然后需要你求一个序列上的最优分割点j的问题你大概率会写出一个 O(n²) 的算法。然后一看数据范围n 是 10⁵ 甚至 10⁶直接超时。这时候你可能会想有没有办法把内层循环的 O(n) 优化掉变成 O(1) 或者 O(log n) 的决策斜率优化Slope Optimization就是为了解决这类问题而生的。我第一次遇到这类问题是在做“任务安排”类的题目时状态转移方程大概是dp[i] min{ dp[j] (sumT[i] S) * (sumC[i] - sumC[j]) }其中sumT和sumC是前缀和。最直观的想法就是遍历所有j i取最小值。当 n 很大时这显然不可行。斜率优化的本质是把原本需要遍历比较的决策过程转化成一个在平面上维护凸包Convex Hull并通过比较斜率来快速剔除劣质决策点的几何问题。听起来有点抽象但它的核心思想非常直观在众多候选决策中有些决策是永远不可能成为最优解的我们可以提前把它们淘汰掉。为什么叫“斜率优化”因为在转化后的几何模型里判断一个决策点是否优于另一个决策点关键在于比较两条直线的斜率。这个技巧能将许多形如dp[i] min{ dp[j] f(i) * g(j) h(i) k(j) }的方程优化到 O(n) 或 O(n log n)。它不像单调队列优化那样有固定的“窗口”概念而是通过维护决策点的“凸性”来保证高效性。掌握它相当于在 DP 优化武器库里增加了一件重型装备。2. 从代数到几何斜率优化的数学模型建立要理解斜率优化我们必须先完成一次关键的思维转换将状态转移方程从纯粹的代数比较转化为几何图形上的点与线。我们以一个经典模型为例假设状态转移方程为dp[i] min{ dp[j] a[i] * b[j] }其中j i且a[i]是随i单调递增的这是应用斜率优化的常见前提之一。对于固定的ia[i]是常数。我们把min去掉把方程改写为dp[i] dp[j] a[i] * b[j]。这可以进一步变形为dp[j] (-a[i]) * b[j] dp[i]。现在请你盯着这个式子看dp[j] (-a[i]) * b[j] dp[i]。它像什么它是一条直线的方程在这个方程里自变量x 是b[j]。因变量y 是dp[j]。斜率k 是-a[i]。截距b 是dp[i]。这意味着对于每一个已经计算出来的决策点j我们可以在平面直角坐标系上画出一个点P_j: (b[j], dp[j])。而我们当前要计算的dp[i]实际上是在寻找一条斜率为k_i -a[i]的直线穿过某个已知点P_j后得到的截距最小的那条直线。因为截距dp[i]正是我们要最小化的目标。所以整个动态规划的过程就变成了每计算出一个dp[j]就在坐标系里添加一个点(b[j], dp[j])。当要计算dp[i]时我们已知斜率k_i -a[i]。我们需要从已有的所有点中找到那个能让穿过它的、斜率为k_i的直线截距最小的点。如果还是觉得抽象我们可以代入具体数字。假设已有三个决策点 P1: (b[1]2, dp[1]5) P2: (b[2]4, dp[2]7) P3: (b[3]6, dp[3]6)现在要计算i4且a[4]3即斜率k -3。我们画三条斜率都为 -3 的直线分别穿过 P1, P2, P3过 P1 的直线y -3*(x-2) 5 截距dp[i] 5 6 11过 P2 的直线y -3*(x-4) 7 截距dp[i] 7 12 19过 P3 的直线y -3*(x-6) 6 截距dp[i] 6 18 24显然过 P1 的直线截距最小所以最优决策j1dp[4]11。这个过程如果暴力做就是 O(n)。但几何给了我们更快的视角。2.1 凸包与最优决策点关键问题来了是不是所有点都有可能成为最优决策点答案是否定的。有些点被其他点“完全包围”在任何斜率下都不会成为最优。我们需要维护一个点集使得其中的点在几何上构成一个“下凸壳”Lower Convex Hull。什么是下凸壳想象我们用一根橡皮筋从下方套住所有点橡皮筋最终接触到的那些点连成的折线就是下凸壳。对于寻找最小截距当斜率k单调时我们关心的是下凸壳。如何判断一个点是否应该留在凸壳中假设我们按x坐标即b[j]递增的顺序加入新点。维护一个点队列。当加入新点P_new时我们检查队列末尾的两个点P_{k-1}和P_k与P_new的关系。如果P_k在P_{k-1}到P_new的连线上方那么P_k就是一个“凸点”应该保留如果P_k在连线下方或线上那么P_k对于构成下凸壳是无效的应该被弹出队列。这个判断可以通过计算叉积Cross Product或者比较斜率来完成。更常用的判断方法是比较斜率。设队列末尾两点为(x1, y1),(x2, y2)新点为(x3, y3)。当(y2 - y1) / (x2 - x1) (y3 - y2) / (x3 - x2)时说明P2不在下凸壳上需要弹出。为了避免除法精度问题通常写成乘法形式(y2 - y1) * (x3 - x2) (y3 - y2) * (x2 - x1)。注意这里对应维护下凸壳求最小截距如果要求最大截距则维护上凸壳判断条件为。2.2 斜率单调性下的决策剔除建立了凸包后我们如何快速找到对于当前斜率k_i的最优决策点如果查询的斜率k_i是单调的例如本题假设a[i]单调增则k_i -a[i]单调减那么最优决策点在凸壳上也是单调移动的。具体来说我们维护一个决策指针或直接操作队列头部。对于下凸壳和单调递减的斜率k最优决策点j是使得穿过P_j和P_{j1}的直线斜率第一个小于等于当前斜率k_i的那个点j。因为斜率更小的直线更“平缓”在当前斜率下能给出更小的截距。判断条件设队列头部的两点为P_j (x_j, y_j)和P_{j1} (x_{j1}, y_{j1})。如果(y_{j1} - y_j) / (x_{j1} - x_j) k_i那么对于斜率k_i来说P_{j1}比P_j更优或一样优因此我们可以将P_j从队列头部弹出。一直弹到上述不等式不成立为止此时队列头部的点就是最优决策点。同样使用乘法形式避免除法(y_{j1} - y_j) k_i * (x_{j1} - x_j)。为什么从几何上理解(y_{j1} - y_j) / (x_{j1} - x_j)是凸壳上相邻两点连线的斜率。如果这个斜率小于等于我们手中的直线斜率k_i说明凸壳在P_j处比我们的直线更“平”。我们要找的是凸壳上第一个斜率大于等于k_i的线段左侧的点对于下凸壳求最小截距。当k_i单调递减时这个最优决策点只会向右移动不会向左所以可以单调队列维护。3. 经典例题实战任务安排洛谷P2365 / AcWing 301理论讲了很多我们用一个最经典的题目来串起整个流程。题目大意有 N 个任务排成序列每个任务有完成所需时间T_i和费用系数C_i。执行一批任务前需要启动时间 S。执行一批任务[j1, i]的费用为这批任务的完成时刻启动时间这批任务总时间乘以这批任务费用系数之和。目标是最小化总费用。我们定义sumT[i]为时间的前缀和。sumC[i]为费用系数的前缀和。dp[i]表示处理完前i个任务的最小费用。状态转移考虑最后一批任务是从j1到i。那么dp[i] min{ dp[j] (S * (sumC[N] - sumC[j]) (sumT[i] - sumT[j]) * (sumC[i] - sumC[j]) }。这里S * (sumC[N] - sumC[j])是启动时间对后续所有任务包括i之后的产生的额外费用这是一个经典的费用提前计算思想。为了简化我们令st[i] sumT[i],sc[i] sumC[i]。方程写为dp[i] min{ dp[j] S * (sc[N] - sc[j]) (st[i] - st[j]) * (sc[i] - sc[j]) }其中0 j i。展开并整理与j相关的项dp[i] min{ dp[j] S*sc[N] - S*sc[j] st[i]*sc[i] - st[i]*sc[j] - st[j]*sc[i] st[j]*sc[j] }对于固定的iS*sc[N]和st[i]*sc[i]是常数可以提到min外面。我们关注min里面的部分dp[j] - S*sc[j] - st[i]*sc[j] - st[j]*sc[i] st[j]*sc[j]这个式子看起来复杂但我们可以尝试将其化为Y - k * X的形式。把只与j有关的项视为Y把同时与i和j有关的乘积项拆开让其中一个因子作为斜率k。观察- st[i]*sc[j] - st[j]*sc[i] st[j]*sc[j]。我们希望把st[i]或sc[i]提出来作为斜率。通常选择那个单调的变量作为斜率。这里st[i]和sc[i]都是单调递增的因为时间和费用系数均为正。我们选择st[i]作为斜率k。重新组合与j有关的项 令Y(j) dp[j] - S*sc[j] st[j]*sc[j]X(j) sc[j]那么min里面的式子可以写为Y(j) - st[i] * X(j) - st[j]*sc[i]。糟糕这里多出了一个- st[j]*sc[i]它无法融入Y(j) - k*X(j)的形式因为st[j]和sc[i]都是变量。这说明我们最初的方程形式不够“标准”。我们需要更严格的“斜率优化”标准形式。让我们回到原始方程并采用更常见的费用提前计算的写法dp[i] min{ dp[j] st[i] * (sc[i] - sc[j]) S * (sc[N] - sc[j]) }。这里S*(sc[N]-sc[j])是j之后所有任务包括i因这次启动多付的费用。将常数项S*sc[N]提出dp[i] min{ dp[j] - (S st[i]) * sc[j] } st[i]*sc[i] S*sc[N]现在对于固定的i令k_i S st[i]单调递增b[j] sc[j]单调递增。那么min里面的部分就是dp[j] - k_i * b[j]。这等价于求min{ dp[j] - k_i * b[j] }。我们把它写成直线截距的形式dp[j] k_i * b[j] B其中B就是dp[i]减去常数项的部分。为了最小化dp[i]我们需要最小化截距B即最大化-B。但更直观地我们直接处理min{ dp[j] - k_i * b[j] }。我们可以令y(j) dp[j],x(j) b[j] sc[j]。那么问题转化为给定一系列点(x(j), y(j))和斜率k_i找一条斜率为k_i的直线穿过某个点使得该直线的截距y(j) - k_i * x(j)最小。看这就是我们第二节中推导出的标准形式只不过这里的“截距”是y - kx而之前是y kx b中的b。本质是一样的。3.1 代码实现与逐行解析假设我们已经预处理了st[i]和sc[i]。下面是核心的 DP 循环部分使用单调队列维护下凸壳。#include iostream #include cstring using namespace std; typedef long long LL; const int N 300010; // 根据题目数据范围 int n, s; LL st[N], sc[N]; LL dp[N]; int q[N]; // 单调队列存储决策点下标 j int main() { cin n s; for (int i 1; i n; i) { cin st[i] sc[i]; st[i] st[i-1]; sc[i] sc[i-1]; } int hh 0, tt 0; // 队列初始化通常放入决策点 0 q[0] 0; // dp[0] 0 是一个合法的决策起点 for (int i 1; i n; i) { // 1. 维护队列头找到最优决策点 j // 条件 (dp[q[hh1]] - dp[q[hh]]) (s st[i]) * (sc[q[hh1]] - sc[q[hh]]) // 即斜率 (y2-y1)/(x2-x1) k_i while (hh tt (dp[q[hh1]] - dp[q[hh]]) (s st[i]) * (sc[q[hh1]] - sc[q[hh]])) { hh; // 弹出队头因为 q[hh1] 更优 } int j q[hh]; // 最优决策点 // 2. 计算 dp[i] dp[i] dp[j] st[i] * (sc[i] - sc[j]) s * (sc[n] - sc[j]); // 3. 将点 i 加入决策集合维护凸壳 // 条件 (dp[i] - dp[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]) (dp[q[tt]] - dp[q[tt-1]]) * (sc[i] - sc[q[tt]]) // 即斜率 (y_i - y_tt) / (x_i - x_tt) (y_tt - y_{tt-1}) / (x_tt - x_{tt-1}) // 注意这里比较的是加入 i 点后队列末尾两点 (tt-1, tt) 的斜率是否小于等于新两点 (tt, i) 的斜率 // 乘法形式避免除法注意 long long 防止溢出 while (hh tt (dp[i] - dp[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]) (dp[q[tt]] - dp[q[tt-1]]) * (sc[i] - sc[q[tt]])) { tt--; // 弹出队尾不满足下凸性 } q[tt] i; // 加入新决策点 } cout dp[n] endl; return 0; }逐行解析关键点初始化q[0]0。因为dp[0]0对应点(sc[0], dp[0]) (0, 0)这是一个合法的决策起点。寻找最优决策点队头维护while (hh tt (dp[q[hh1]] - dp[q[hh]]) (s st[i]) * (sc[q[hh1]] - sc[q[hh]])这个条件就是判断(Y(q[hh1]) - Y(q[hh])) / (X(q[hh1]) - X(q[hh])) k_i。其中Y(j)dp[j],X(j)sc[j],k_i S st[i]。如果成立说明点q[hh1]比q[hh]更优对于当前斜率k_i所以弹出q[hh]。循环结束后q[hh]就是使得截距dp[j] - k_i * sc[j]最小的j。状态转移直接用找到的j计算dp[i]。加入新点并维护凸壳队尾维护while (hh tt (dp[i] - dp[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]) (dp[q[tt]] - dp[q[tt-1]]) * (sc[i] - sc[q[tt]])这个条件判断的是队列末尾三点q[tt-1],q[tt],i是否构成“上凸”注意我们维护的是下凸壳所以要剔除上凸的点。设三点为 A(q[tt-1]), B(q[tt]), C(i)。向量 AB (Xb-Xa, Yb-Ya)向量 BC (Xc-Xb, Yc-Yb)。判断 AB 到 BC 是否“左转”即叉积 0。在斜率表示下就是判断(Yb-Ya)/(Xb-Xa) (Yc-Yb)/(Xc-Xb)。如果成立说明 B 点在上凸的位置需要弹出。我们代码里用的是对应维护下凸壳求最小值。如果题目是求最大值需要维护上凸壳则这里的判断应改为。乘法形式是为了避免除法带来的精度问题但要注意乘法的方向确保不等式等价。一个极易出错的细节在队尾维护的while循环判断中不等号的方向与我们是求最小值还是最大值、以及X坐标即sc[j]是否单调递增密切相关。在本例中sc[j]单调增求最小值维护下凸壳使用。如果X坐标单调减不等式方向可能需要调整。最稳妥的方法是画图或者记住维护下凸壳求最小截距时相邻三点应满足斜率递增。如果新点i的加入导致末尾两点斜率大于等于新线段斜率即斜率不再严格递增则弹出队尾。4. 斜率不单调与二分查找前面讨论的情况基于一个关键假设每次查询的斜率k_i是单调的。这样我们才能用单调队列在 O(1) 均摊时间内从队头弹出无用决策。但如果斜率k_i没有单调性呢例如状态转移方程中的a[i]不是单调的。此时我们无法再单调地移动队头指针来剔除决策点因为对于不同的i最优决策点j可能会在凸壳上来回移动。但是我们依然可以维护一个完整的凸壳。因为点的横坐标X(j)通常是b[j]在按j递增的顺序加入时往往是单调的例如前缀和所以凸壳可以用单调栈或双端队列在 O(n) 内维护好。当需要计算dp[i]时问题转化为在一个静态的或动态增长但已维护好的凸壳上找到一点P使得过P点斜率为k_i的直线截距最小或最大。这是一个在凸壳上的查找问题。对于下凸壳求最小截距最优决策点P是凸壳上第一个使得其与后继点连线斜率大于等于k_i的点。因为斜率小于k_i的部分更平缓在当前斜率下截距更大。由于凸壳上的斜率是单调递增的我们可以使用二分查找来定位这个点。具体实现时我们仍然用队列q[]存储凸壳上的点下标。二分查找的check函数就是比较相邻两点的斜率与k_i的大小。设mid为候选点我们需要判断K(q[mid], q[mid1])与k_i的关系。如果K(q[mid], q[mid1]) k_i说明mid点可能就是我们想要的点或者最优点在mid左边我们令r mid。如果K(q[mid], q[mid1]) k_i说明mid点还不够“陡”最优决策点应该在mid右边令l mid 1。最后q[l]就是最优决策点。查找复杂度为 O(log n)总复杂度为 O(n log n)。4.1 代码示例斜率不单调的情况假设状态转移为dp[i] min{ dp[j] (a[i] - b[j])^2 }其中a[i]无单调性b[j]单调递增。展开dp[i] min{ dp[j] a[i]^2 - 2*a[i]*b[j] b[j]^2 }。 对于固定的ia[i]^2是常数。所以等价于求min{ (dp[j] b[j]^2) - 2*a[i]*b[j] }。令Y(j) dp[j] b[j]^2X(j) b[j]k_i 2 * a[i]那么就是求min{ Y(j) - k_i * X(j) }。X(j)单调增k_i无单调性。我们需要维护一个关于点(X(j), Y(j))的下凸壳。由于X(j)单调增凸壳可以在 O(n) 内用单调队列维护队尾弹出不满足凸性的点。但在查询时我们需要二分查找凸壳。// 假设已有预处理好的 b[] 和 a[] LL dp[N]; int q[N], hh, tt; // 计算斜率注意使用 double 或 long double 防止精度问题或者用乘法判断 double slope(int j1, int j2) { double dx b[j2] - b[j1]; if (fabs(dx) 1e-18) return ...; // 处理除零通常 b[] 严格单调则不会 return ( (dp[j2] b[j2]*b[j2]) - (dp[j1] b[j1]*b[j1]) ) / dx; } // 在凸壳 q[hh..tt] 上二分查找最优决策点 int find_optimal(int i) { LL k 2 * a[i]; int l hh, r tt; while (l r) { int mid (l r) 1; // 如果 mid 和 mid1 的斜率小于 k说明 mid 还不够优答案在右边 if (slope(q[mid], q[mid1]) k) { l mid 1; } else { r mid; } } return q[l]; } for (int i 1; i n; i) { // 1. 二分查找最优决策点 int j find_optimal(i); // 2. 状态转移 dp[i] dp[j] (a[i] - b[j]) * (a[i] - b[j]); // 或其他等价形式 // 3. 将 i 作为新决策点加入凸壳 // 维护队尾凸性如果末尾三点不满足下凸则弹出队尾 while (hh tt) { // 判断 (tt-1, tt) 和 (tt, i) 的斜率 // 如果 slope(q[tt-1], q[tt]) slope(q[tt], i)则弹出 q[tt] // 使用叉积或斜率比较注意精度 if ( slope(q[tt-1], q[tt]) slope(q[tt], i) ) { tt--; } else { break; } } q[tt] i; }重要提示在二分查找中我们比较的是斜率。如果X坐标差可能为 0需要特判。在实际竞赛中为了完全避免浮点数精度误差通常会使用叉积进行判断将除法比较转化为乘法比较。例如判断slope(j1, j2) k可以写为(Y2-Y1) k * (X2-X1)。但在二分查找中k是变化的用乘法需要小心。一种更鲁棒的方法是在凸壳上二分查找第一个斜率大于等于k的线段这个比较可以用叉积实现但逻辑稍复杂。许多选手在精度要求不高时直接使用double并设置一个较小的eps。5. 边界条件、精度与实战心得斜率优化虽然强大但实现细节上的坑非常多一不小心就会 WAWrong Answer 或者 TLETime Limit Exceeded。5.1 初始化与边界决策点 0绝大多数序列 DP 问题dp[0]都是一个合法决策代表从开头开始分组。一定要记得将其加入决策队列。对应的点坐标(X(0), Y(0))需要根据定义计算好。队列初始状态通常hh0, tt0且q[0]0。这意味着队列里有一个点。在队头弹出判断时条件是while (hh tt ...)确保队列中至少有两个点时才需要比较斜率。横坐标相等如果不同的决策点j对应的X(j)可能相等那么在计算斜率时会出现除零错误。此时需要特殊处理。通常如果X(j)相等那么Y(j)更小的点更优对于下凸壳求最小值可以直接保留更优的那个点。在维护凸壳时如果新点i的X(i)与队尾点X(q[tt])相等则需要比较Y值决定是替换队尾点还是直接跳过。5.2 精度与比较方式这是斜率优化最棘手的部分之一。浮点数除法直接使用double计算斜率(Y2-Y1)/(X2-X1)最简单但可能有精度误差。在比较slope1 slope2时如果两个斜率非常接近浮点数比较可能出错。对于大多数题目double的精度足够但有些毒瘤数据会卡精度。乘法判断为了杜绝精度问题通常将斜率比较(y2-y1)/(x2-x1) (y3-y2)/(x3-x2)转化为乘法形式(y2-y1)*(x3-x2) (y3-y2)*(x2-x1)。但这里有一个巨大的坑符号我们必须确保乘法的两边是同号的或者处理好异号情况。对于下凸壳X坐标通常是单调递增的所以(x2-x1)和(x3-x2)都是正数。此时不等式两边同时乘以正数(x2-x1)*(x3-x2)不等号方向不变。这是最安全的情况。如果X坐标单调递减那么(x2-x1)和(x3-x2)都是负数乘积为正数不等号方向也不变。但是如果X坐标不是单调的在二分查找凸壳时我们维护的凸壳点X坐标是单调的但查询斜率k_i可能使得比较slope(j, j1) k_i时k_i可能为负且(x_{j1}-x_j)为正直接乘(x_{j1}-x_j)是正数没问题。但如果k_i是表达式且(x_{j1}-x_j)可能为负在非单调X的凸壳二分中不会因为凸壳点X有序就需要分类讨论。最佳实践在X坐标单调的前提下一律使用乘法判断。确保你清楚X的单调性以及你维护的是上凸壳还是下凸壳从而决定不等号方向。溢出问题(y2-y1)*(x3-x2)这类乘法y和x常常是long long范围乘积可能溢出 64 位整数。在 C 中可以使用__int128或者转化为long double进行比较。例如bool check(int j1, int j2, int i) { long double left (long double)(Y(j2)-Y(j1)) * (X(i)-X(j2)); long double right (long double)(Y(i)-Y(j2)) * (X(j2)-X(j1)); // 对于下凸壳维护如果 left right 则弹出 j2 return left right; }使用long double比较可以避免溢出但仍有极小的精度风险。5.3 决策单调性与四边形不等式斜率优化是决策单调性的一种特殊情况。决策单调性是指对于状态i其最优决策点opt[i]随着i增大而单调不减或单调不增。斜率优化问题中如果斜率k_i和横坐标X(j)都单调那么决策点opt[i]是单调的这对应了可以用单调队列维护队头。更一般的决策单调性可以用分治或者单调栈二分的方法解决适用范围比斜率优化更广。而四边形不等式是证明决策单调性的有力工具。对于斜率优化题目我们通常不需要显式地证明四边形不等式只要能把方程化成Y - kX的形式并且X和k有单调性就可以套用模板。5.4 调试技巧打印决策队列在 DP 循环中打印出每个i对应的队列状态q[hh..tt]以及计算出的最优决策j。观察决策点是否单调移动凸壳点坐标是否合理。小数据暴力对拍写一个 O(n²) 的暴力 DP与斜率优化版本对拍。生成随机小数据n1000比较两个程序的dp[n]是否一致。这是最有效的查错方法。检查不等式方向如果答案不对首先怀疑队尾维护凸壳的不等式方向是否写反。可以画三个点手动计算一下看看是应该用还是。记住口诀下凸壳求最小值斜率递增维护时踢掉队尾斜率大于等于新线段斜率的点上凸壳求最大值斜率递减维护时踢掉队尾斜率小于等于新线段斜率的点。但最靠谱的还是画图。检查初始化确认dp[0]的值是否正确以及点(X(0), Y(0))是否已入队。检查溢出和精度对于乘法判断使用long double或__int128来避免溢出。对于浮点数比较使用eps如1e-18。斜率优化是一个“会者不难难者不会”的算法。它的核心在于建模——将代数问题转化为几何问题。一旦转化成功剩下的就是套用维护凸壳和查找最优点的模板。多练习几道经典题目如任务安排、玩具装箱、土地购买、仓库建设等熟悉各种变形就能逐渐掌握这项强大的优化技术。记住关键步骤永远是1) 化简方程分离i和j2) 确定X(j),Y(j),k_i3) 判断X和k的单调性4) 选择单调队列或二分凸壳5) 小心实现注意精度和边界。