斜率优化 DP 学习笔记（P3195 解题报告）

· · 个人记录

斜率优化 DP，这个斜率告诉我们它与一次函数相关。一个东西可以放在一次函数上，那么它就可能挂钩单调性与平面几何。

但是，没有关系！我们还是要学的。

我们使用 P3195 [HNOI2008]玩具装箱 作为例题来理解这个事情。

首先 OI-wiki 上给出了一个简化版题意，接下来我们都从这个题意入手：

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

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

首先我们可以得到一个非常朴素的状态转移方程，这个非常基础。

使 f_i 表示取了前 i 个物品的最小代价。

那么我们很容易得到这个方程：

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

这里的 pre_i=\sum_{j=1}^ic_j，也就是前缀和。前面的 i-j-1 实际上是从 i-(j+1) 变过来的。我们这里的 j 枚举的是 i 所在的段的上一段的最后一个下标。

显然这个 DP 的复杂度高达 O(n^2)，零八年，能过简直是痴心妄想。

那么我们得优化一下它。

首先我们发现那个平方非常无语，所以我们试着把平方打开，但是强行开更加无语，所以我们做一些只是简化形式的记号：

\begin{aligned} s_i&=pre_i+i\\ L'&=L+1 \end{aligned}

那么柿子就可以变一变了，变成这样，我们再给它拆一拆：

\begin{aligned} f_i&=\min\limits_{j<i}\{f_j+(s_i-s_j-L')^2\}\\ &=\min\limits_{j<i}\{f_j+s_j^2-2s_j(s_i-L')+(s_i-L')^2\}\\ &=\min\limits_{j<i}\{f_j+s_j^2+2s_j(L'-s_i)\}+(s_i-L')^2 \end{aligned}

这一步的精髓就是分离 i 相关与 j 相关的部分。之所以我可以这样概括是因为斜率优化 DP 通常都是一层循环枚举下标，内层循环得到一个最值去更新外层的 DP 值，那么我们的重点关注对象就是这个内层取最值的部分（实际上，这部分也是我们方程的主体）。我们把最值柿子的 i 和 j 分离开，原因是之和 i 相关的部分我们根本就不用带到最值循环里去算，这是为了斜率优化的处理。

于是我们一通操作，得到了这样的柿子：

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

接下来我们非常高级的，把它丢到一次函数上。考虑一次函数解析式 y=kx+b\to b=y-kx。我们斜率优化的目的是把每个 j 对应成二维平面上的 (x_j,y_j)，在我们知道 b_i 和 k_i 的情况下去操作。

提示：ZYH 今天两次犯傻。对于一条直线，它的截距其实就是它与 y 轴交点的值。请牢记这个非常基础的定义，避免头晕。

那么这里我们可以做这样的对应：

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

接下来我们考虑分割 kx 这一坨，有如下的规则：

那么这里我们又以做这样的对应：

\begin{aligned} k_i&=-2(L'-s_i)\\ x_j&=s_j \end{aligned}

那么我们的柿子就可以变成 b_i=\min\limits_{j<i}\{y_j-k_ix_j\}。

很明显每一组 (x_j,y_j,k_i) 可以确定一条直线。我们的目的变成找到这一堆直线里面截距最小的那个，而且我们要得到的是它的下标。

我们的问题已经成为了一个简单计算几何的问题，接下来我们就从计算几何方面来解决这个问题。

首先有一个这样的性质，我们把这个问题考虑成一条斜率 k_i 的直线，从右向左移动，然后在这个平面里面碰点。第一个碰到的点就是答案点。感性理解，剩下的点肯定需要我继续往左移才能碰到，我这个直线越向左，它与 y 轴交点就越大，也就是截距越大。再进一步，一条直线向左移其实等于一条直线向上移，所以你这个向左其实等于沿着 y 轴逐渐升高。

注意这个性质必须满足 x 单调，否则你不能说剩下的点必须更左才能找到。这是斜率优化的一个要求。

假设这些点构成一个凸包，那么这个点肯定在凸壳上。由于这里是最小值，所以从右向左滑动那条直线，那么这个点肯定在下凸壳；反之找最大值，这条直线就从左向右滑，这个点就在上凸壳。

下凸壳性质告诉我们，如果两个点 (x_a,y_a) 和 (x_b,y_b) 相接，而 (x_b,y_b) 有和另外一个点 (x_c,y_c) 相接，又定义 K(a,b) 表示点 a,b 间直线的斜率，那么我们一定可以得到 K(a,b)<K(b,c)。

我们需要做的，就是在一堆编号为 [l,r] 之间的点里面找到那么一个点 g 满足 K(g-1,g)\leqslant k_i<K(g,g+1)，这里的一个小于等于一个小于是为了不让相等的情况同时归属到两种情况。当然如果 g=l 或者 g=r 的时候我们要特别判断一下。

那么我们怎么找到这个 g 呢？我们发现如果 k_i 飘忽不定，那么我们就要用平衡树之类的睿智玩意儿去找这个 g 了，然而本题中 k_i 绑定了 s_i，s_i 存在单调递增，那么 -s_i 单调递减，前面又有一个 -2，那么负负得正，k_i 存在单调递增。

那也就是说我们前面用不到的 g 后面都不可能再用了了。具体来说，对于斜率小于 k_i 的在队首的需要弹掉，然后考虑将 i 放进队列尾，为了维护下凸壳性质，如果凸壳中最后一条线（队列中最后两点连线）斜率大于队尾与 i 连线的斜率，就需要弹掉队尾。画一个下凸壳并考虑斜率为 k_i 的线在斜率增大或减小时碰到凸壳的情况，以及新加入的 i 点如何使凸壳不合法，可以很轻松的得知弹队首或队尾的条件。

我们的具体操作如下：

那么这个问题就被我们解决了。它的时间复杂度为 DP 的 O(n) 转移加上这个类似单调队列的玩意儿的总和 O(n) 复杂度，是线性的，非常不错。

我们发现如果 k_i 飘忽不定，那么我们就要用平衡树之类的睿智玩意儿去找这个 g 了。

如果这里没有 k_i 单调性，也就是所谓的 k_i 飘忽不定的时候，我们怎么做呢？

首先我们的问题是对于这个 k_i 要尽快地找到一个点 g 满足 K(g-1,g)\leqslant k_i<K(g,g+1)，那不妨将它转化为找到一个小于等于 k_i 的最大斜率。很明显那个斜率就可以帮助我们对应出 g。面对最小的最大，我们不妨考虑二分，而恰好下凸壳是单调的，所以可以这么搞。

例如 P5785 [SDOI2012]任务安排，首先你需要使用到 P2365 任务安排中的柿子，然后根据 ZYH 的草稿中该题的柿子推理，我们可以发现这里由于负 t 的出现，sum 就不单调了，随即 y 也就不单调了。那么这里就是我们所述的特殊情况。

我们直接上一个二分就可以解决问题，时间复杂度只是多了个 \log。要注意一下二分判断队列中 mid 点的时候为了防止数组越界需要判断它与队列中 mid+1 点的斜率与目前的 k 的关系。为了防止答案在 tail 导致找不到答案需要先把 ans\gets tail。

P5785 的题解中有较好的图片，实在理解不了的时候可以去看。

我们前面说的是下凸壳，现在来说上面的。我们在弹前面线段的时候，发现上凸壳的斜率是逐渐变小的，与下凸壳是一样的，所以弹队首的 while 中的符号无需变号。

但是我们在后面加点以保证凸壳性质的时候，由于上凸壳在后端逐渐变小，而下凸壳是在后端逐渐变大，所以这个弹队尾的 while 需要变号。

这样就可以处理最大值了。