前言
在动态规划的转移时，我们时常遇到形如 $f(i)=\min\limits_{j < i}{f(j)}+w$ 的转移，这种转移可以用单调队列维护以做到线性的复杂度。斜率优化同样也是通过不断删去不合法和不优决策来优化 DP。
例题引入
HNOI2008 玩具装箱 LG3195
题目大意
有 $n$ 个玩具，价值为 $c_i$ ，要求将这些玩具分段，每段的价值为 $(r-l+\sum\limits_{i=l}^rc_i-L)^2$ 。
思路
不难列出下列状态转移方程
$$
f(i)=\min_{1\le j< i}{f(j)+(i-(j+1)+\sum_{k=j+1}^ic_k-L)^2}
$$
和式可以用前缀和 $sum$ 求得，设 $L’=L+1$ ，化简可得
$$
f(i)=\min_{1\le j< i}{f(j)+(i-j+sum(i)-sum(j)-L’)^2}
$$
设 $s_i=sum_i+i$ ，可得
$$
f(i)=\min_{1\le j< i}{f(j)+(s(i)-s(j)-L’)^2}
$$
这样做朴素转移是 $O(n^2)$ 的，考虑优化。
基本思想
以题目为例，展开得
$$
f(i)=\min_{1\le j< i}{f(j)+s(i)^2+L^2+s(j)^2-2s(i)s(j)-2s(i)L’+2s(j)L’}
$$
将只与 $i$ 有关的项和常数项移到左边，得
$$
f(i)-s(i)^2-L^2+2s(i)L’=\min_{1\le j< i}{f(j)+s(j)^2-2s(i)s(j)+2s(j)L’}
$$
至此，我们将这个问题转移到平面直角坐标系中，将一次转移看作一条线段，将未知量 $j$ 看作线段上的一个点，将式子转化得
$$
f(i)-s(i)^2-L^2+2s(i)L’=\min_{1\le j< i}{f(j)+s(j)^2-2(s(i)-L’)s(j)}
$$
考虑直线的表达式 $y=kx+b$ ，转化得 $b=y-kx$ ，带入到上式中可得
$$
\begin{cases}
x=s(j)\\
y=f(j)+s(j)^2\\
k=2(s(i)-L’)\\
b=f(i)-s(i)^2-L^2+2s(i)L’
\end{cases}
$$
原式转化为
$$
b=\min{y-kx}
$$
也就是说，我们想要最小化一条斜率已知的直线的截距。
于是我们可以将这条直线不断向上平移，直到经过决策点集的其中一个点。如下图所示
考虑这些点有哪些性质。
发现对于任三个横坐标递增的点，会存在 $2$ 种情况，如图所示
我们把形似左图斜率不断增大的点集称为下凸包，右图斜率不断减小的点集称为上凸包，我们发现，右图的中间点不可能作为最优决策，左图的中间点有可能作为最优决策。所以这道题的决策点集在一个下凸包上。
不难发现，如果下凸包存在一个点 $j$ ，$ j$ 左侧的斜率 $<$ 当前 $i$ 的斜率 $<$$j$ 右侧的斜率，则 $j$ 为 $i$ 的最优决策点。
形象化的说，若当前的下凸包集合为 $S$ ，则最优决策点的下标 $p$ 应满足
$$
\text{slove}(S_{p-1},S_p) < k_i < \text{slove}(S_p, S_{p+1})
$$
其中 $\text{slove}$ 表示两点之间的斜率。
由于 $k,x$ 是单调递增的，所以我们可以通过一些方式，及时删掉决策中不优的点，以保证时间复杂度。
考虑用单调队列 $q$ 优化，$l$ 表示队头， $r$ 表示队尾，实现方式如下：
- 队列中先保存 $0$ 这个点，以构成一条线段；
- 将 $\text{slove}(q_l,q_{l+1}) < k_i$ 的队头弹出，保证决策最优；
- 用队头更新答案；
- 将 $\text{slove}(q_{r-1},q_r) > \text{slove}(q_r,i)$ 的队尾弹出，以维护下凸包；
- 将 $i$ 压入队尾。
由于每个点至多入队出队一次，时间复杂度均摊 $O(1)$ ，总时间复杂度 $O(n)$ 。
代码
1 |
|
小结
这个算法应用各元素的比值，从而快速维护 DP 的转移。由于比值类似坐标系中的斜率，我们将这种 DP 优化方式称为斜率优化。
例题
JSOI2011 柠檬 LG5504
题目大意
有 $n$ 个大小为 $s_i$ 的贝壳，你可以选择一些不交的区间 $[l,r]$ ，对于每个区间，你可以选择一个大小 $s_0$ ，你可以获得 $s_0T^2$ 个柠檬，$ T$ 是 $[l,r]$ 中大小为 $s_0$ 的贝壳的个数。求最多能获得的柠檬数。
思路
不难发现，在最优策略中，对于每一个区间 $l,r$ ，必定满足 $s_l=s_r$ ，不然一定比分开选不优。
设 $[1,i]$ 中有 $c_i$ 个大小为 $s_i$ 的贝壳，$ f(i)$ 为 最大获得的柠檬数，可以列出状态转移方程
$$
f(i)=\max_{1\le j < i,s_i=s_j}{f(j-1)+s_i(c_i-c_j+1)^2}
$$
同样考虑斜率优化，先化简可得
$$
f(i)=\max_{1\le j < i,s_i=s_j}{f(j-1)+s_i+2s_ic_i+s_ic_i^2-2s_ic_j-2s_ic_ic_j+s_ic_j^2}
$$
注意到 $s_i=s_j$ ，可得
$$
f(i)-s_i-2s_ic_i-s_ic_i^2=\max_{1\le j < i,s_i=s_j}{f(j-1)-2s_jc_j+s_jc_j^2-2s_ic_ic_j}
$$
此时
$$
\begin{cases}
x=c_j\\
y=f(j-1)-2s_jc_j+s_jc_j^2\\
k=2s_ic_i\\
b=f(i)-s_i-2s_ic_i-s_ic_i^2
\end{cases}
$$
由于这里要维护 $\max$ ，就相当于维护一个上凸包。由于上凸包的斜率是单调递减的，故最优决策点要满足 $\text{slove}(S_p,S_{p+1}) < k_i < \text{slove}(S_{p-1}, S_p)$ ，故将所有满足 $\text{slove}(S_{p-1}, S_p)<k_i$ 的 $p$ 弹出集合，同时 $k$ 是单调递增的，此时集合内的斜率均 $> k_i$ ，取出直接转移即可。发现所有操作均在队尾执行，直接用单调栈维护即可。
二分维护整个凸包
SDOI2012 任务安排 LG5785
题目大意
有 $n$ 个任务，第 $i$ 个任务需要 $T_i$ 的时间完成，要求将 $n$ 个任务依次分为若干批，每批开始前需要 $s$ 的时间，完成这批任务的时间为所有任务时间的总和（同一批任务结束时间相同），每个任务的价值为 $C_i$ 乘上该任务完成的时间，求一个最优方案，使总价值最小。
思路
考虑 DP，设 $f(i)$ 表示 $1\sim i$ 的最小总价值。对于新增的一段 $[j+1,i]$ ，要对之后所有段产生贡献，对当前段也产生了贡献，可列出状态转移方程为
$$
f(i)=\min_{1\le j < i}{f(j)+S\sum_{k=j+1}^nC_k+\sum_{k=1}^iT_k\times\sum_{k=j+1}^iC_k}
$$
用前缀和代替和式可得
$$
f(i)=\min_{1\le j < i}{f(j)+S(sumC_n-sumC_j)+sumT_i(sumC_i-sumC_j)}
$$
这样转移是 $O(n^2)$ ，考虑转化成斜率优化的形式，即
$$
f(i)-SsumC_n-sumT_isumC_i=\min_{1\le j < i}{f(j)-(S+sumT_i)sumC_j)}
$$
此时
$$
\begin{cases}
x=sumC_j\\
y=f(j)\\
k=S+sumT_i\\
b=f(i)-SsumC_n-sumT_isumC_i
\end{cases}
$$
若 $T_i>0$ ，可以直接套板子解决，而这题中 $T_i$ 可以为负数，说明 $k$ 不是单调递增的，则我们不能通过弹出队头来保证答案最优，并且队头也不一定是最优决策点。
考虑维护整个凸包，由于下凸包中的斜率是单调递增的，所以可以在凸包中二分找到满足 $\text{slove}(S_{p-1},S_p) < k_i < \text{slove}(S_p, S_{p+1})$ 的点，然后常规从队尾入队即可。
代码
1 | int n, s, dp[MAXN], f[MAXN], t[MAXN], q[MAXN], l = 1, r = 1; |
扩展
在上述例题中，题目均保证了横坐标 $x_i$ 单调，然而在一些毒瘤题中，题目并不保证 $x_i$ 或 $k_i$ 单调，此时需要通过一些奇妙的数据结构维护整个凸包。
CDQ 分治
CDQ 分治，即基于时间的分治算法，其基本思想为
- 对于区间 $[l,r]$，递归分治 $[l,mid]$ 与 $[mid+1,r]$。
- 计算左半区间的修改对右半区间的影响。
借助 CDQ 分治，我们可以先处理左半区间，维护左半部分的凸包，更新右半部分的答案，再处理右半区间，最后以 $x_i$ 为关键字归并排序。
至此，维护凸包时我们保证了 $x_i$ 单调，我们就可以用队列/栈维护凸包，同时保证了时间复杂度的正确性。
对于时间复杂度，有递推式
$$
T(n)=2T\left(\frac{n}{2}\right)+O(n)
$$
根据主定理，可得最终时间复杂度为 $\Theta(n\log n)$。
SDOI2012 基站建设
思路
根据勾股定理
$$
(r_{1,i}+r_{2_j})^2=(r_{2,i} - r_{1,j})^2+(x_i-x_j)^2\to \sqrt{r_{2,i}}=\frac{x_i-x_j}{2\sqrt{r_{1,j}}}
$$
可列出状态转移方程
$$
f_i=\min_{j<i}{f_j+\frac{x_i-x_j}{2\sqrt{r_{1,j}}}}+v_i
$$
此时有
$$
\begin{cases}
x=\dfrac{1}{2\sqrt{r_{1,j}}}\\
y=f_j-\dfrac{x_j}{2\sqrt{r_{1,j}}}\\
k=-x_i\\
b=f_i-v_i
\end{cases}
$$
此时 $x$ 不单调，可以用 CDQ 分治维护。
代码
1 | const int MAXN = 5000000 + 5; |
李超线段树
李超线段树，即标记持久化的线段树，可以在线维护类似下列的问题
- 在平面中插入一条线段。
- 求一个区间内所有线段纵坐标的最小值。
- 对于横坐标 $x$，求所有线段中纵坐标的最小值。
算法流程
对于区间 $[l,r]$，定义这个区间的最优线段为
- 定义域包括 $[l,r]$。
- 在 $x=mid$ 时纵坐标最小。
在我们在 $[l,r]$ 上插入一条线段 $v$，将其与原最优线段 $u$ 比较，如图所示，分 $4$ 种情况。
设 $x=mid$ 时两条线段的取值分别为 $res_v$ 与 $res_u$，则有
$k_u<k_v\land res_u>res_v$
如图所示，此时最优线段为 $v$，同时用 $u$ 更新左半区间（右半区间必定为 $v$）
$k_u<k_v\land res_u<res_v$
如图所示，此时最优线段为 $u$，同时用 $v$ 更新右半区间（左半区间必定为 $u$）
$k_u>k_v\land res_u>res_v$
如图所示，此时最优线段为 $v$，同时用 $u$ 更新右半区间（左半区间必定为 $v$）
$k_u>k_v\land res_u<res_v$
如图所示，此时最优线段为 $u$，同时用 $v$ 更新左半区间（右半区间必定为 $u$）
此外对于 $k_u=k_v$，只需比较 $u$ 与 $v$ 的截距即可。
在查询时，不断更新当前区间最优值，并向下递归即可。
关于时间复杂度，由于一个区间会被分成 $O(\log n)$ 个区间，每个区间需要 $\Theta(\log n)$ 修改，所以总时间时间复杂度为 $O(n\log^2 n)$。
代码
1 | //LG 4097 |
那么，如何用李超线段树来维护凸包，其优点在于何处，下面给出一道例题。
CF932F Escape Through Leaf
题目大意
给定一棵树，根为 $1$，每次操作可以从 $u$ 走到 $v$，获得的价值为 $a_v\times b_u$，且满足 $u$ 在 $v$ 的子树内，求对于每一个终点的最小总代价。
$n,|a_i|,|b_i|\le 10^5$
思路
首先有一个很显然的 $O(n^2)$ DP，即
$$
f(u)=\min{f(v)+a_ub_v}\qquad v \in subtree(u)
$$
显然可以斜率优化，但与常规方法不同的是，我们钦定使纵坐标最小，则有
$$
\begin{cases}
x=a_u\\
y=f(u)\\
k=b_v\\
b=f(v)
\end{cases}
$$
这要求我们在每次转移时要插入一条斜率为 $b_v$，截距为 $f(v)$ 的直线，且回溯时将 $v$ 上的线段树合并到 $u$ 上，可以用动态开点李超线段树合并实现。
代码
1 | const int MAXN = 1e5 + 5; |
通过这道例题，可以发现李超线段树可以很好的处理树上的斜率优化 DP，并且不需要满足单调的性质，可拓展性好。
此外，还可以用平衡树维护凸包，但过程复杂且常数较大，这里不再赘述。
分段函数
序列sequence
题解
首先有一个显然的 $O(n^2)$ 的 DP，即
$$
f(i,j)=\min_{k\le j}{f(i-1,k)}+|a_i-j|
$$
定义序列函数
$$
f_i(x)=\begin{cases}
0&i=0\\
\min\limits_{p\le x}{f_{i-1}(p)}+|a_i-x|&i>0
\end{cases}
$$
则有
$\forall i\in \mathbf{N}^*$，$f_i(x)$ 构成一个下凸包。
证明
当 $i=1$ 时，$f_1(x)=|a_1-x|$ 为一个分段函数，在 $x=a_1$ 时取得最小值，此时必定构成一个下凸包。
当 $i>1$ 时，假定 $f_{i-1}(x)$ 构一个下凸包，即证 $f_i(x)$ 构成一个凸包。
根据 $f(x)$ 的定义，$f_i(x)$ 由一系列一次函数构成，考虑当前一次函数的斜率 $k$ 与 $a_i$ 对一个转移过程中的影响。
$k<0,x\le a_i$
由于 $f_{i-1}(x)$ 是下凸的，所以当 $k<0$ 时，$f_{i-1}(x)$ 单调递减。此时 $f_{i-1}(x)$ 的前缀最小值在 $x$ 处取到。则有
$$
f_i(x)=f_{i-1}(x)+a_i-x
$$
此时，将 $f_{i-1}(x)$ 转化为一次函数的形式，则这个区间上的转移相当于 $k\gets k-1$，即斜率递减 $1$。$k<0,x> a_i$
同第一种情况，我们得到
$$
f_i(x)=f_{i-1}(x)-a_i+x
$$
同样这里相当于 $k\gets k+1$，即斜率递增 $1$。$k\ge 0,x\le a_i$
当 $k\ge 0$ 时，$f_{i-1}(x)$ 单调不降。此时设 $f_{i-1}(x)$ 的最小值在 $op$ 处取到，设最小值为 $\gamma$。则有
$$
f_i(x)=\gamma+a_i-x
$$
对于某一个特定的 $f_{i-1}(x)$，$\gamma$ 唯一，故这里相当于 $k\gets -1$，即将斜率变为 $-1$。$k\ge 0,x > a_i$
同情况 3，可得
$$
f_i(x)=\gamma-a_i+x
$$则 $k\gets 1$，即将斜率变为 $1$。
现在考虑在 $f_{i-1}\to f_i$ 的转移中，可能会出现的情况，如图所示，存在 $2$ 种情况。
!GRAPH
$a_i < op$
如图所示，此时的转移会出现情况 1，2，4 这三种。
- 对于 $x\in [1, op]$：$x\in[1, a_i]$ 时较小的斜率更小，$x\in (a_i, op]$ 时较大的斜率更大，且必定 $\le 0$。
- 对于 $x\in (op, +\infty)$：斜率恒定不变为 $1$，必定大于 $[1,op]$ 中所有斜率不大于 $0$。
$a_i \ge op$
如图所示，此时的转移会出现情况 1，3，4 这三种。
- 对于 $x\in [1, op]$：所有斜率递减 $1$，且必定 $< -1$。
- 对于 $x\in (op, +\infty)$：$x\in(op, a_i]$ 时，斜率恒定不变为 $-1$，必定大于 $[1,op]$ 中所有斜率小于 $-1$。$x\in (a_i, +\infty)$ 时，斜率恒定不变为 $1$，同样满足条件。
综合以上两种情况，我们可以得出若 $f_{i-1}(x)$ 下凸，则 $f_i(x)$ 下凸。即原命题得证。$\square$
有这个性质之后我们发现，我们要求 $\min{f_n(x)}$，且对于 $f_{i-1}\to f_i$ 的转移中，斜率 $>0$ 的区间对答案没有贡献，可以直接将这一段舍去，则函数的最小值在 $x$ 最大时取到。
考虑维护一个堆，存 $f_i(x)$ 的每一个拐点，考虑每次插入 $a_i$ 对答案的影响。
$a_i\ge op$
此时决策点为 $a_i$，答案不变，将 $a_i$ 插入堆（$f_i(a_i)=f_{i-1}(op)+|a_i-a_i|$）。
$a_i<op$
如图所示，此时由于新决策点 $op’$ 与 $op$ 之间的斜率为 $0$，可以弹出 $op$，直接更新答案（$f_i(op’)=f_i(op)=f_{i-1}(op)+|a_i-op|$）。
!GRAPH
至此，我们可以用一个及其简洁的代码实现上列过程。