1. 从暴力到优雅斜率优化DP的思维跃迁搞算法竞赛或者研究动态规划优化的朋友对“斜率优化”这四个字应该不陌生。它经常出现在一些看似简单的序列分割、任务安排问题里但数据范围一大朴素的O(n²) DP就会立刻超时。我第一次遇到这类问题是在处理一个经典的生产线调度模型上题目大意是有一批任务需要按顺序处理每个任务有准备成本和执行成本任务可以分批每批有一个固定的启动开销目标是让总成本最小。写了个二维DP一交上去就TLE看着n10^5的数据范围直挠头。后来啃了半天论文和题解才把“斜率优化”这个工具真正装进自己的工具箱。今天这篇笔记就结合我踩过的坑和刷过的题把斜率优化DP的核心思想、推导细节、代码模板以及那些容易写错的边界情况掰开揉碎了讲清楚。无论你是正在备赛的选手还是对算法优化感兴趣的开发者相信这篇都能帮你打通任督二脉。简单说斜率优化是用来解决一类特定状态转移方程优化问题的技术。这类方程通常长这样dp[i] min{ dp[j] f(j) * g(i) h(i) c(j) }其中min或max括号里的东西能通过变形变成一个关于f(j)和dp[j] c(j)的线性表达式。它的核心思想是把每个决策点j想象成平面上的点(x, y)把状态i的转移看作是用一条固定斜率的直线去切这些点找最优截距。听起来有点抽象别急我们一步步来。2. 问题模型与暴力DP的瓶颈我们从一个最经典的模型开始讲起这样更有抓手。假设有n个任务每个任务有一个权值a[i]任务必须按顺序完成。现在要把这些任务分成若干连续组批每完成一组会产生一个代价这个代价由该组任务的权值总和以及一个与分组方式有关的函数决定。很多实际问题都能抽象成这个模型比如任务分批问题每组有固定的启动时间或成本S第j1到第i个任务作为一组时代价为S sum(a[j1:i]) * T(i)其中T(i)可能与i有关。打印文章/书籍排版每行有固定宽度一行内单词间的空格会产生一个丑陋度目标是使总丑陋度最小。这其实就是著名的“序列分割”问题。仓库建设/物流运输在一条直线上有n个地点需要选择若干地点建仓库货物从产地运到仓库有费用建仓库也有费用目标是总费用最小。这类问题最直观的DP设计是设dp[i]表示处理完前i个任务的最小总代价。sum[i]为前缀和即sum[i] a[1] a[2] ... a[i]。 那么转移方程通常可以写成dp[i] min{ dp[j] w(j1, i) }其中0 j iw(j1, i)表示将区间[j1, i]的任务分为一组所产生的代价。暴力DP的瓶颈就在于这个min操作需要枚举所有可能的j复杂度是O(n²)。当n达到10^5甚至更大时这显然是不可接受的。斜率优化要做的就是利用代价函数w的特殊形式将转移优化到O(n)或O(n log n)。为了让推导更具体我们使用一个最经典、最标准的斜率优化模型作为例子假设代价函数为w(j1, i) (sum[i] - sum[j])^2 C其中C是一个常数。 那么状态转移方程为dp[i] min{ dp[j] (sum[i] - sum[j])^2 C } 其中0 j i 我们约定sum[0] 0, dp[0] 0。3. 代数变形从min到直线方程斜率优化的第一步也是关键的一步是进行代数变形将转移方程中与i和j相关的项分离。我们对目标转移式进行展开和变形假设对于当前要计算的dp[i]最优决策点是j。那么有dp[i] dp[j] (sum[i] - sum[j])^2 C展开平方项dp[i] dp[j] sum[i]^2 - 2*sum[i]*sum[j] sum[j]^2 C移项将与j无关的项移到左边dp[i] - sum[i]^2 - C dp[j] sum[j]^2 - 2*sum[i]*sum[j]观察这个等式。右边同时包含了i和j。我们进行一个关键的换元令y(j) dp[j] sum[j]^2x(j) sum[j]k(i) 2 * sum[i]b(i) dp[i] - sum[i]^2 - C于是上面的等式变成了一个标准的直线方程形式b(i) y(j) - k(i) * x(j)这个变形的意义何在现在对于每个已经计算出来的状态j我们可以在二维平面上确定一个点P_j (x(j), y(j))即(sum[j], dp[j] sum[j]^2)。 对于当前要计算的状态i我们有一条斜率固定为k(i) 2 * sum[i]的直线。b(i)就是这条直线在y轴上的截距。 我们的目标dp[i] min{...} 根据变形后的等式b(i) y(j) - k(i)*x(j) 等价于对于给定的斜率k(i)找一点P_j使得过P_j且斜率为k(i)的直线的截距b(i)最小因为dp[i] b(i) sum[i]^2 C后两项是常数最小化dp[i]等价于最小化b(i)。注意这里有一个非常重要的前提我们要求k(i)是单调的x(j)也是单调递增的。在这个例子中因为sum[i]是前缀和如果a[i]非负那么sum[i]和k(i)都是单调递增的。这个单调性是后续能用单调队列将复杂度降到O(n)的关键。如果k(i)不单调则需要用更复杂的数据结构如平衡树、CDQ分治来维护凸壳复杂度为O(n log n)。4. 几何直观与凸壳维护理解了代数变形的几何意义我们就进入了斜率优化的核心维护一个“下凸壳”。什么是凸壳想象平面上有一系列点P_j。一个点集的下凸壳就是连接最左点和最右点并且所有点都在连线之上或之上的折线。更技术地说是这些点按x坐标排序后相邻点连线斜率单调递增的那条“下包络线”。为什么是最小化截距对于一条斜率为k的直线我们要让它尽可能往下移减小截距b直到碰到某个点。这个“碰到的点”就是所有点中使得y - k*x最小的那个点。从几何上看如果把这条直线从负无穷远处向上平移它第一次触碰到的点就是最优决策点。如何快速找到这个点如果所有决策点P_j构成了一个下凸壳那么对于单调递增的斜率k(i)最优决策点也在凸壳上单调移动。这就像用一根斜率不断变大的棍子从凸壳的左下端开始向右上方“扫”过去棍子与凸壳的切点就是最优决策点。维护凸壳的具体操作单调队列实现我们用一个双端队列q[]来维护构成下凸壳的点存储的是点的编号j我们可以通过j得到x(j), y(j)。检查队首有效性维护决策单调性 对于当前状态i其斜率k(i)是固定的。队列中保存了多个候选点。如果队列前两个点q[head]和q[head1]构成的直线的斜率slope(q[head], q[head1]) k(i)那么对于斜率更大的k(i)来说点q[head]永远不可能成为最优决策因为直线会先碰到q[head1]所以可以将队首q[head]弹出。重复此过程直到队列头两个点构成的斜率大于k(i)。此时队首q[head]就是当前状态i的最优决策点j。计算dp[i] 利用队首j q[head]直接代入转移方程计算dp[i]。同时计算出新点P_i的坐标(x(i), y(i))。将新点P_i加入凸壳维护凸壳性质 将点i加入队列尾部。但加入前需要检查加入后是否会破坏凸壳的“下凸”性质。设队列尾部三个点依次为q[tail-1],q[tail],i。我们需要保证从q[tail-1]到q[tail]的斜率小于从q[tail]到i的斜率。如果slope(q[tail-1], q[tail]) slope(q[tail], i)那么点q[tail]就在q[tail-1]和i的连线之上或共线它就不是凸壳上的点了应当从队尾弹出。重复此过程直到满足凸壳性质再将i加入队尾。斜率计算的细节与防误差 斜率通常用浮点数计算但为了避免精度误差在竞赛中普遍采用交叉相乘的方法进行比较。 假设有两个点P1(x1, y1),P2(x2, y2) 斜率s12 (y2 - y1) / (x2 - x1)。 比较s12 k 等价于(y2 - y1) k * (x2 - x1)。 比较s12 s23 等价于(y2 - y1)*(x3 - x2) (y3 - y2)*(x2 - x1)。 这样全程使用整数运算避免了浮点误差。5. 代码模板与逐行解析下面给出针对我们例子dp[i] min{ dp[j] (sum[i] - sum[j])^2 C }的完整C斜率优化DP代码模板并附上详细注释。#include bits/stdc.h using namespace std; typedef long long ll; // 通常需要long long防止溢出 const int MAXN 1e5 10; int n; ll C, a[MAXN], sum[MAXN], dp[MAXN]; int q[MAXN]; // 单调队列存储决策点下标j int head, tail; // 队首队尾指向下一个可插入位置 // 计算点j的纵坐标y inline ll Y(int j) { return dp[j] sum[j] * sum[j]; // y(j) dp[j] sum[j]^2 } // 计算点j的横坐标x inline ll X(int j) { return sum[j]; // x(j) sum[j] } // 计算斜率 (y2-y1)/(x2-x1) 通过交叉相乘比较 inline bool slope_check(int j1, int j2, int j3) { ll x1 X(j1), y1 Y(j1); ll x2 X(j2), y2 Y(j2); ll x3 X(j3), y3 Y(j3); // 判断 slope(j1, j2) slope(j2, j3) ? // 即 (y2-y1)/(x2-x1) (y3-y2)/(x3-x2) ? // 交叉相乘注意这里可能溢出确保使用long long return (y2 - y1) * (x3 - x2) (y3 - y2) * (x2 - x1); } int main() { // 假设输入n, C, 以及数组a[1..n] cin n C; for (int i 1; i n; i) { cin a[i]; sum[i] sum[i - 1] a[i]; // 计算前缀和 } // 初始化队列0号状态一个任务都没处理作为初始决策点 head tail 0; q[tail] 0; // 将点0入队 dp[0] 0; for (int i 1; i n; i) { // 1. 维护队首弹出斜率小于等于当前k(i)的点 // k(i) 2 * sum[i] // 判断 slope(q[head], q[head1]) 2*sum[i] ? // 即 (Y(q[head1]) - Y(q[head])) 2*sum[i] * (X(q[head1]) - X(q[head])) while (head 1 tail Y(q[head 1]) - Y(q[head]) 2 * sum[i] * (X(q[head 1]) - X(q[head]))) { head; } int j q[head]; // 最优决策点 // 2. 计算dp[i] dp[i] dp[j] (sum[i] - sum[j]) * (sum[i] - sum[j]) C; // 3. 将新点i加入队列维护凸壳下凸性质 // 判断队尾两点和i的斜率关系如果尾部点不满足下凸则弹出 while (head 1 tail slope_check(q[tail - 2], q[tail - 1], i)) { tail--; } q[tail] i; // 将i加入队尾 } cout dp[n] endl; return 0; }模板使用要点X(j),Y(j)函数需要根据你具体的变形公式来写。核心是找到变形后b y - k*x中的x和y。slope_check函数是比较斜率用于维护凸壳。注意不等号方向这里维护的是下凸壳斜率单调递增所以当slope(j1, j2) slope(j2, j3)时需要弹出j2。如果维护的是上凸壳求最大值斜率单调递减不等号方向可能相反。队首维护时的比较是与当前状态的斜率k(i)比较。同样需要注意不等号方向目标是找到第一个斜率大于k(i)的线段对应的左端点。初始状态dp[0]通常需要预先定义好并加入队列。6. 经典例题分析与变种掌握了模板我们来看几个变种理解如何将不同问题“转化”到斜率优化的框架下。例题1任务安排洛谷P2365题目描述有N个任务排成序列必须按顺序完成。将任务分成若干批每批包含连续若干个任务。第i个任务单独完成所需时间是T[i]费用系数是C[i]。每批任务开始前需要启动时间S。同一批任务在同一时刻完成每个任务的完成时刻就是其所在批的结束时刻。每个任务的费用是其完成时刻乘以费用系数。求最小总费用。推导过程设dp[i]为处理完前i个任务的最小费用。sumT[i],sumC[i]为时间和系数的前缀和。如果将从j1到i的任务作为一批那么这一批的结束时间是sumT[i] S * (批次数)。这里批次数不好直接表示。一个经典技巧是“费用提前计算”。考虑当前批j1到i的启动时间S它会对本批及之后所有任务产生额外的费用。我们可以把S产生的费用提前加到当前决策中。转移方程dp[i] min{ dp[j] sumT[i]*(sumC[i]-sumC[j]) S*(sumC[n]-sumC[j]) }其中0 j i。变形dp[i] min{ dp[j] - (sumT[i]S)*sumC[j] } sumT[i]*sumC[i] S*sumC[n]。令y(j) dp[j],x(j) sumC[j],k(i) sumT[i] S。目标是最小化dp[j] - k(i)*sumC[j]即b y - k*x的最小值。注意这里k(i)是单调递增的因为sumT[i]递增x(j)也是单调递增的因为sumC[i]递增。直接套用下凸壳模板即可。例题2玩具装箱洛谷P3195题目描述略。其标准转移方程为dp[i] min{ dp[j] (i - j - 1 sum[i]-sum[j] - L)^2 }。 通过将sum[i]加上iL加上1令s[i] sum[i] i,L’ L 1可以转化为dp[i] min{ dp[j] (s[i] - s[j] - L’)^2 }。 展开后变形为dp[i] s[i]^2 min{ (dp[j] s[j]^2 2*L’*s[j]) - 2*s[i]*s[j] } (s[i]^2 L’^2 2*s[i]*L’)。 令y(j) dp[j] s[j]^2 2*L’*s[j],x(j) s[j],k(i) 2*s[i]。又回到了标准形式。实操心得遇到复杂式子不要慌。核心步骤永远是1) 写出原始DP方程2) 将min/max括号内关于i和j的项分离特别是把含有i*j交叉项的系数整理出来3) 将与j相关的部分通常是dp[j]和一些只含j的表达式视为y将与j相关且与i相乘的项中的j的部分视为xi的系数视为斜率k4) 检查x和k的单调性决定维护凸壳的方式。7. 边界条件、陷阱与调试技巧即使理解了原理实现时也容易踩坑。下面是我总结的几个常见陷阱1. 队列初始化问题通常需要将初始状态比如j0加入队列。务必确保这个初始点的x,y计算正确并且dp[0]的值符合题目定义。有时dp[0]可能不为0。2. 斜率比较的等号问题在维护凸壳队尾弹出时如果遇到三点共线的情况即slope(j1, j2) slope(j2, j3)是否需要弹出j2对于求最小值下凸壳通常需要弹出。因为中间的j2点对于后续任何斜率都不会成为最优决策它被两端的点“支配”了保留它只会让凸壳多一个点增加不必要的判断。所以在slope_check函数中我们使用而非。对于求最大值上凸壳同理使用。3. 除零与溢出除零在计算斜率时如果x坐标可能相等直接除法会导致除零错误。这就是为什么必须用交叉相乘来比较斜率的原因。交叉相乘完美避免了除法。溢出y和x可能很大做乘法时(y2-y1)*(x3-x2)很可能超出int范围。务必使用long long。在极端情况下甚至可能需要__int128或手写高精度比较。4. 单调性假设不成立怎么办如果斜率k(i)不是单调的我们就不能用单调队列在O(1)内弹出队首了。此时有两种主流方法二分查找在凸壳仍然用队列/数组维护上二分查找第一个斜率大于k(i)的位置。复杂度 O(n log n)。CDQ分治更通用的方法可以处理x(j)和k(i)都不单调的情况。其思想是“离线”处理通过分治将动态插入点和查询的过程转化为静态问题。复杂度也是 O(n log n)。5. 调试技巧打印队列状态在每次循环中打印出队列里的点下标j以及计算出的x(j), y(j)。手动画图看看这些点是否真的构成了一个凸壳。对拍写一个 O(n²) 的暴力DP用小数据n1000随机生成大量测试用例比较两种方法的结果是否一致。这是最可靠的调试方法。检查变形最怕的是变形公式推错了。可以随机固定一个i和几个j分别用原始公式和变形后的y - k*x公式计算值看是否只差一个常数。8. 从一次翻车案例看思维闭环最后分享一个我印象深刻的翻车案例。当时做一道题转移方程是dp[i] max{ a[i]*b[j] c[j] }其中a[i]单调递减b[j]单调递增。我一看这形式很像y kx b啊ka[i],xb[j],yc[j]。于是兴冲冲地开始维护凸壳。结果一直WA。排查了很久才发现问题我要求的是最大值。对于直线y kx b给定斜率k找最大截距b。这等价于b y - kx的最大值。而我之前维护的是下凸壳求最小值时用的。对于最大值应该维护上凸壳斜率单调递减。修正方法在维护队尾凸壳性质时将slope_check的不等号从改为。在维护队首时因为k(i)即a[i]是单调递减的所以最优决策点会向左移动。判断条件需要从“斜率小于等于当前k”弹出改为“斜率大于等于当前k”弹出。这个案例给我的教训是永远明确目标是求min还是max。求min对应最小化截距维护下凸壳求max对应最大化截距维护上凸壳。明确k(i)和x(j)的单调性。这决定了维护队首是用单调队列O(1)弹出还是二分查找O(log n)。推导时最好把变形后的式子写成b y - kx的形式。这样目标是最小化/最大化b几何意义非常清晰就是用过点(x, y)、斜率为k的直线的截距。斜率优化本质上是一种数学建模和数据结构优化的结合。它要求我们先把问题抽象成合适的DP模型然后通过代数变形发现其几何本质最后用合适的数据结构单调队列/栈、二分、平衡树来加速查询。这个过程锻炼的不仅是编码能力更是分析和转化的思维能力。多练习几种典型模型总结出自己的变形套路和代码模板再遇到这类问题时你就能一眼看穿本质快速写出正确的代码。