斜率优化

例题引入

「HNOI2008」玩具装箱

有个玩具，第个玩具价值为。要求将这个玩具排成一排，分成若干段。对于一段，它的代价为 $(r-l+\sum_{i=l}^r c_i-L)^2$ 。其中是一个常量，求分段的最小代价。

$1\le n\le 5\times 10^4, 1\le L, c_i\le 10^7$ 。

朴素的 DP 做法

令表示前个物品，分若干段的最小代价。

状态转移方程： $f_i=\min_{j<i}\{f_j+(i-(j+1)+pre_i-pre_j-L)^2\}=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}$ 。

其中表示前个数的和，即 $\sum_{j=1}^i c_j$ 。

该做法的时间复杂度为，无法解决本题。

优化

考虑简化上面的状态转移方程式：令，则 $f_i=\min_{j<i}\{f_j+(s_i-s_j-L')^2\}$ 。

将与无关的移到外面，我们得到

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

考虑一次函数的斜截式，将其移项得到。我们将与有关的信息表示为的形式，把同时与有关的信息表示为，把要最小化的信息（与有关的信息）表示为，也就是截距。具体地，设

\begin{aligned} x_j&=s_j\\ y_j&=f_j+s_j^2\\ k_i&=-2(L'-s_i)\\ b_i&=f_i-(s_i-L')^2\\ \end{aligned}

则转移方程就写作 $b_i = \min_{j<i}\{ y_j-k_ix_j \}$ 。我们把看作二维平面上的点，则表示直线斜率，表示一条过的斜率为的直线的截距。问题转化为了，选择合适的（ $1\le j<i$ ），最小化直线的截距。

slope_optimization

如图，我们将这个斜率为的直线从下往上平移，直到有一个点在这条直线上，则有，这时取到最小值。算完，我们就把这个点加入点集中，以做为新的 DP 决策。那么，我们该如何维护点集？

容易发现，可能让取到最小值的点一定在下凸壳上。因此在寻找的时候我们不需要枚举所有个点，只需要考虑凸包上的点。而在本题中随的增加而递增，因此我们可以单调队列维护凸包。

具体地，设表示过和的直线的斜率。考虑队列 $q_l,q_{l+1},\ldots,q_r$ ，维护的是下凸壳上的点。也就是说，对于，始终有 $K(q_{i-1},q_i) < K(q_i,q_{i+1})$ 成立。

我们维护一个指针来计算最小值。我们需要找到一个 $K(q_{e-1},q_e)\le k_i< K(q_e,q_{e+1})$ 的（特别地，当或者时要特别判断），这时就有，即是的最优决策点。由于是单调递减的，因此的移动次数是均摊的。

在插入一个点时，我们要判断是否 $K(q_{r-1},q_r)<K(q_r,i)$ ，如果不等式不成立就将弹出，直到等式满足。然后将插入到队尾。

这样我们就将 DP 的复杂度优化到了。

概括一下上述斜率优化模板题的算法：

将初始状态入队。
每次使用一条和相关的直线去切维护的凸包，找到最优决策，更新。
加入状态。如果一个状态（即凸包上的一个点）在加入后不再是凸包上的点，需要在加入前将其剔除。

接下来我们介绍斜率优化的进阶应用，将斜率优化与二分/分治/数据结构等结合，来维护性质不那么好（缺少一些单调性性质）的 DP 方程。

二分/CDQ/平衡树优化 DP

当我们在这个点寻找最优决策时，会使用一个和相关的直线去切我们维护的凸包。切到的点即为最优决策。

在上述例题中，直线的斜率随单调变化，但是对于有些问题，斜率并不是单调的。这时我们需要维护凸包上的每一个节点，然后每次用当前的直线去切这个凸包。这个过程可以使用二分解决，因为凸包上相邻两个点的斜率是有单调性的。

玩具装箱改

有个玩具，第个玩具价值为。要求将这个玩具排成一排，分成若干段。对于一段，它的代价为 $(r-l+\sum_{i=l}^r c_i-L)^2$ 。其中是一个常量，求分段的最小代价。

$1\le n\le 5\times 10^4,1\le L\le 10^7,-10^7\le c_i\le 10^7$ 。

本题与「玩具装箱」问题唯一的区别是，玩具的价值可以为负。延续之前的思路，令表示前个物品，分若干段的最小代价。

状态转移方程： $f_i=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}$ 。

其中 $pre_i = \sum_{j=1}^i c_j$ 。

将方程做相同的变换

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

然而这时有两个条件不成立了：

直线的斜率不再单调；
每次加入的决策点的横坐标不再单调。

仍然考虑凸壳的维护。

在寻找最优决策点，也就是用直线切凸壳的时候，我们将单调队列找队首改为：凸壳上二分。我们二分出斜率最接近直线斜率的那条凸壳边，就可以找到最优决策。

在加入决策点，也就是凸壳上加一个点的时候，我们有两种方法维护。

第一种方法是直接用平衡树维护凸壳。那么寻找决策点的二分操作就转化为在平衡树上二分，插入决策点就转化为在平衡树上插入一个结点，并删除若干个被踢出凸壳的点。此方法思路简洁但实现繁琐。

下面介绍一种基于 CDQ 分治的做法。

设 $\text{CDQ}(l,r)$ 代表计算 $f_i,i\in [l,r]$ 。考虑 $\text{CDQ}(1,n)$ ：

我们先调用 $\text{CDQ}(1,mid)$ 算出 $f_i,i\in[1,mid]$ 。然后我们对这个区间内的决策点建凸壳，然后使用这个凸壳去更新 $f_i,i\in [mid+1,n]$ 。这时我们决策点集是固定的，不像之前那样边计算 DP 值边加入决策点，那么我们就可以把 $i \in [mid+1,n]$ 的先按照直线的斜率排序，然后就可以使用单调队列来计算 DP 值了。当然，也可以在静态凸壳上二分计算 DP 值。
对于中的每个点，如果它的最优决策的位置是在这个区间，在这一步操作中他就会被更新成最优答案。当执行完这一步操作时，我们发现中的所有点已经发挥了全部的作用，凸壳中他们存不存在已经不影响之后的答案更新。因此我们可以直接舍弃这个区间的决策点，并使用 $\text{CDQ}(mid+1,n)$ 解决右区间剩下的问题。

时间复杂度 $O(n\log^2 n)$ 。

对比「玩具装箱」和「玩具装箱改」，可以总结出以下两点：

二分/CDQ/平衡树等能够优化 DP 方程的计算，于一定程度上降低复杂度，但不能改变这个方程本身。
DP 方程的性质会取决于数据的特征，但 DP 方程本身取决于题目中的数学模型。

小结

斜率优化 DP 需要灵活运用，其宗旨是将最优化问题转化为二维平面上与凸包有关的截距最值问题。遇到性质不太好的方程，有时需要辅以数据结构来加以解决，届时还请就题而论。

习题

本页面最近更新：2023/2/18 07:57:07，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, StudyingFather, Ir1d, luoguyuntianming, Marcythm, sshwy, wood3, abc1763613206, BackSlashDelta, billchenchina, Chrogeek, ChungZH, fps5283, GavinZhengOI, greyqz, GreyTigerOIer, Henry-ZHR, hsfzLZH1, Konano, Luckyblock233, MrFoodinChina, nanmenyangde, ouuan, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用