斜率优化可以在动态规划中根据斜率的性质优化时间。

当转移出现$a_i\times b_j$的时候，单调队列优化不再适用，就要使用斜率优化。

例题

[HNOI2008]玩具装箱
给定$n$个玩具，每个玩具价值$C_i$，分成若干段，定义分段代价$cost(i,j)=(j-i+\sum_{k=i}^jC_j -L)^2,i\leq j$,$L$为给定常数,求分段的最小代价和。
$1\leq n \leq 5\times 10^4,1\leq L,C_i\leq 10^7$

---

朴素做法

$f_i$表示前$i$个物品分段的最小代价,$pre_i$为价值前缀和。

$f_i=\min_{j<i}\{f_j+(i-j-1+pre_i-pre_j-L)^2\}$

时间复杂度$O(n^2)$，无法通过本题。

优化

设$s_i=i+pre_i$,$L=L+1$

$f_i=\min_{j<i}\{f_j+(s_i-s_j-L)^2\}=\min_{j<i}\{f_j+(s_i-L)^2+2(L-s_i)s_j+s_j^2\}$

$f_i-(s_i-L)^2=\min_{j<i}\{f_j+s_j^2+2s_j(L-s_i)\}$

将$f_i-(s_i-L)^2$看作$b_i$，$f_j+s_j^2$看作$y_j$，$s_j$看作$x_j$，$-2(L-s_i)$看作$k_i$，就有

$b_i=\min_{j<i}\{y_j-k_ix_j\}$

将$(x_j,y_j)$看作坐标系的点，于是转换成定斜率过一点求最小截距。

几个性质：

1. 最优决策点在下凸壳，可以直接维护凸包。
2. 本题的斜率单调递增。
3. 决策单调性：$cost(i,j)=(s_i-s_j-L)^2$是四边形不等式(同时斜率单增也可证明)。

所以可以用单调队列维护一个凸包，具体做法如下：

1. 弹队首，条件为队首代表线段斜率小于 $k_i$，此时选下一个点肯定更优。

2. 队首为最优决策点，更新(决策单调性)。

3. 加入$(x_i,y_i)$决策点，出队当且仅当新的凸包不包含队尾节点(比较斜率)。

4. 加入当前决策点。

复杂度$O(n)$，完美解决。

code on Luogu

进阶

如果斜率不单调怎么办？即决策也不单调。

但这仍然满足最优决策点在凸包上，且新增决策点x单增，我们仍然维护凸包上的点，对于给定斜率$k$，最优决策点一定是在凸包上的直线刚恰好切上凸包的点，满足单调性，故可以用二分答案去找最优决策点。

[SDOI2012]任务安排
将$n$个任务分段并顺序完成，给定完成时间$T$和费用系数$C$，完成一段前需冷却$s$，完成时间为这段时间之和，每个任务的价值为完成时间$\times$费用系数，最小化价值和。
$1 \leq n \leq 3 \times 10^5,1\leq s \leq 2^8,|T_i|\leq 2^8,0 \leq C_i\leq 2^8$

---

先看$O(n^2)$的做法，$f_i$表示前$i$个任务的最小价值和。

最朴素做法中需要一维分了几组的状态，本题不要求分组数量，故有所多余。

这里有个trick：转移的时候，根据乘法分配率，对$[j,i]$分组，$i$以后的任务都多了一个$s\times C_i$的价值，可以直接加上去,于是转移就分为准备时间的贡献和做任务的贡献,这时转移的时候就不必计算当前批任务的具体完成时间，改为计算不计冷却的完成时间。

设时间前缀$pt_i$,价值前缀$pc_i$

$f_i=\min_{j < i}\{f_j+pt_i\times(pc_i-pc_j)+s\times(pc_n-pc_i)\}$

优化

$f_i=\min_{j<i}\{f_j+pt_ipc_i-pt_ipc_j+pc_ns-pc_is\}$

$f_i-pt_ipc_i-pc_ns+pc_is=\min_{j<i}\{f_j-pt_ipc_j\}$

$b_i=f_i-pt_ipc_i-pc_ns+pc_is$

$y_j=f_j,x_j=pc_j,k_i=pt_i$

$b_i=\min_{j<i}\{y_j-k_ix_j\}$

这里由于$T_i$可负，斜率不再单调，但$x$仍然单调，利用上文做法，运用二分答案找最优决策点。

复杂度$O(nlogn)$

再进阶

如果$x$也不单调怎么办，维护凸包就不能用队列维护，但我们有平衡树！但是实现比较繁琐。(代码能力太弱)

以玩具装箱题目为例子，这里$|C_i|\leq 10^7$。

我们发现只需要使$x,k$单调就能用基础做法解决问题，可以使用创造单调性的利器CDQ分治创造单调性，具体的：例如分治$[l,r]$，加入决策点$[l,mid]$，更新状态$[mid+1,r]$，右侧没有考虑到的决策点会在向右递归的时候处理到，且$[l,mid]$的状态的答案一定已经处理完全，所以正确性得证，复杂度$O(nlog^2n)$，多出的$log$在于左区间$x$的排序和右区间$k$的排序。

练习题

鸽子待出

参考资料

• OIwiki-斜率优化