斜率优化
2025-12-13
Intro
Tricks
斜率优化通常有以下几个步骤:
- 分析
寻找出这个问题的一般解决方式,保证正确性。 - 优化
对正确代码的转换进行等价变形,优化复杂度。
Examples
Acwing 300. 任务安排1
提示
容易发现,我们每次增加一批任务会对后面造成影响,考虑将影响提前处理。
如果当前批次结束是 ci,则对后面造成的变化量是 S×(ci+1+ci+2+⋯+cn)
我们先来考虑状态设计:
- 状态集合:fi 表示完成前 i 个任务的所有方案的花费
- 状态属性:max
- 状态转移:考虑依据上一批次的最后一个进行分类。
具体的,令 sti=j=1∑j=itj, sci=j=1∑j=icj:
fi=0≤j<imin{fj+sti×(sci−scj)+S×(scn−scj)}
由于范围只有 5000,可以直接过掉(这道题是后面的前置)。
Acwing 301. 任务安排2
题目传送门
令 0≤j<i,考虑继续对上面的状态转移方程进行变形:
fifi=min{fj+sti×(sci−scj)+S×(scn−scj)}=min{fj−scj×(sti+S)+sti×sci+S×scn}
这个时候,先暂时扔掉 min,将 fj 和 scj 分在方程左右两侧:
fj=(sti+S)×scj+fi−sti×sci−S×scn
容易发现,这是一个形如 y=kx+b 的一次函数,我们可以将其放到一个平面直角坐标系中。
当 i 固定时,这个函数的斜率(sti+S)也是固定的,且截距中 fi 的系数为 1,要求最小的 fi 等价于让截距最小,放在图上也就是从下往上这条线第一次碰到的点即为最佳 fj。 
这张图里,每一个点代表一个形如 (scj,fj) 的点对,但我们不能每一个都判断。
怎么办?注意到 ti,ci 都是正整数,所以斜率大于零小于正无穷,我们钦定三个点 A, B, C,其中 scA<scB<scC,fA<fC。
这个时候可以画出 B 在 AC 所在直线的上侧或下侧,会形成上凸或下凸,但有用的情况应该是:
scB−scAfB−fA<scC−scBfC−fB
(其实就是斜率)
这个时候,我们要维护的也就变成了连接两侧相邻线段斜率单调递增的下凸壳。
哪个点才是我们要找到的转移点呢?如果一条直线斜率为 k,如果某个顶点左侧线段斜率小于 k,右侧线段斜率大于 k,则该顶点就是最优决策。换言之,就是这个凸包上第一个右侧斜率大于 k 的点。
到这里可能会考虑二分,但我们可以继续挖掘题目的特殊性质:
- 斜率单调递增。
这个函数的斜率为 sti+S 且 sti>0。 - 新的点一定在凸包右侧被加入。
由于 ci>0,所以 sci 单调递增且我们以 sci 作为横坐标。
由于这两个性质,我们可以在寻找点时删除所有斜率小于当前直线斜率的点;添加时由于在最右边,这个点一定不会被删掉,可以直接添加,同时将所有不在凸包上的点删掉。
每个点只会进队列出队列一次,所以这个算法是 O(n) 的。
AcWing 302. 任务安排3
题目传送门
与上一题相比,主要变化为 ti 可以为负数,也就是说这条直线的斜率可能为负。
如果这样的话,我们就不能把这个下凸壳前面的点删掉(斜率不具有单调性),可以使用二分查找寻找第一个斜率大于 k 的线段。
AcWing 303. 运输小猫
题目传送门
读完题目,令 di=j=1∑iDj。
额外的,我们设 ai=ti−di(带走第 i 只猫的最早出发时间为 ai)。 这样的话,一个出发时间为 j 的饲养员带走第 i 只猫的时间应为 j+di,也就是猫的等待时间为 j−ai。
这个时候我们如果按照 ai 排序,会发现每个饲养员一定带走连续的若干只猫(带走最后一只的可以带走所有猫)。
但是怎么快速处理带走一段小猫的等待时间呢?我们可以令 si=j=1∑iaj,假如要带走 k+1∼j 只小猫,所有等待时间应为 aj×(j−k)−(sj−sk)。
考虑完这些,我们来进行状态设计:fi,j 表示到第 i 个饲养员,带走前 j 只猫的所有方案的最小值。
状态转移可以直接套上面的公式,即 fi,j=0≤k<jmin{fi−1,k+aj×(j−k)−(sj−sk)}。
这个时候把 i 看为定值,j 为状态变量,k 为决策变量,且出现了 aj×(j−k) 这样的东西,考虑进行斜率优化。
首先把 min 脱掉,将原方程进行变形(将只与 k 有关的放左边,j 和 k 乘积项放右边,其他作为截距):
fi−1,k+sk=aj×k+fi,j−j×aj+sj
这是一个以 k 为横坐标,以 fi−1,k+sk 为纵坐标,斜率为 aj 的一次函数,当截距取最小值时 fi,j 有最小值。
由于 aj>0,所以我们要维护一个下凸壳(斜率单调递增),又因为 aj 单调递增,可以直接像前一道题一样维护一个单调队列。
重要
这里需要注意一下,斜率优化仅优化状态变量 j,也就是每次都需要清空单调队列。
