一种 dp 优化

前置知识

单调队列优化 dp，计算几何基础知识，小学数学。

斜率优化

在 dp 中，我们常常能遇到一类转移方程，其中含有 $i$ 相关的项与 $j$ 相关的项的乘积，形如这种形式：

f_i=\max_{j<i}\{ f_j+a_ib_j\}

我们常见的单调队列优化只能优化只含 $j$ 项的方程，对于这种方程无能为力。因此我们需要利用斜率优化。

先来看一道例题：

任务安排

$n$ 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。

从零时刻开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间为 $t_i$ 。在每批任务开始前，机器需要启动时间 $s$ ，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

每个任务的费用是它的完成时刻乘以一个费用系数 $c_i$ 。请确定一个分组方案，使得总费用最小。

数据范围： $n\le 5000, t_i, c_i>0$ 。

加强版： $n\le 100000,t_i, c_i>0$ 。

先设 $sumT[i]$ 为 $t_i$ 的前缀和， $sumC[i]$ 为 $c_i$ 的前缀和。

我们可以很容易设计出一个 $O(n^3)$ 的转移方程：设 $f[i][j]$ 为前 $i$ 个任务共分为 $j$ 段的最小花费。我们就可以列出转移：

f[i][j]=\min_{k<i}\{ f[k][j - 1]+(sumT[i]+j\times s)\times(sumC[i]-sumC[k])\}

因为状态数为 $O(n^2)$ 级别，无论如何优化都无法通过加强版

因为时间复杂度太高，我们考虑重新设计状态。设 $f[i]$ 为前 $i$ 个任务分为若干段的最小花费，则

f[i]=\min _{j<i}\{f[j]+sumT[i]\times (sumC[i]-sumC[j])+s\times (sumC[n]-sumC[j]) \}

这个方程运用了一个费用提前计算的思想，最后一项 $s\times (sumC[n]-sumC[j])$ 表示虽然不知道后面分成了多少段，但是知道当前分这一段会对后面这些项造成这么多影响。这个方程的复杂度为 $O(n^2)$ ，可以通过原版数据范围。

为了通过加强版，我们化简一下式子。

\begin{aligned} f[i] & = \min _{j<i}\{f[j]+sumT[i]\times (sumC[i]-sumC[j])+s\times (sumC[n]-sumC[j]) \}\\ &=\min _{j<i}\{f[j]+sumT[i]\times sumC[i]-sumT[i]\times sumC[j]+s\times sumC[n]-s\times sumC[j]) \}\\ &=\min _{j<i}\{f[j]-(sumT[i]+s)\times sumC[j]) \}+sumT[i]\times sumC[i]+s\times sumC[n] \end{aligned}

我们移一下项，变为：

f[i]-sumT[i]\times sumC[i]-s\times sumC[n]=\min _{j<i}\{f[j]-(sumT[i]+s)\times sumC[j]) \}

这时就无法化简了，我们考虑下有什么性质。

我们可以设 $x_j=sumC[j], y_j=f[j], k_i=(sumT[i]+s), b_i=f[i]-sumT[i]\times sumC[i]-s\times sumC[n]$ 。（注意下标）这时式子变为：

b_i=\min _{j<i}\{y_j-k_i\times x_j \}

这就变成了一个一次函数求截距的式子。注意到 $sumT[i]\times sumC[i]-s\times sumC[n]$ 在 $i$ 固定时为定值，目前要求 $f[i]$ 最小值，则问题转化为求截距的最小值。

我们可以把问题放到坐标系中来看：

由于 $i$ 固定，则斜率 $k_i$ 固定。我们就可以把问题想象成拿着一条斜率为 $k_i$ 的直线从下往上平移，第一个到达的点（点的坐标为上面的 $(x_j, y_j)$ ）则为最佳转移点（这时截距最小）。我们再考虑下什么样的点才能成为最佳转移点。

考虑三个决策点 $i, j, k(i<j<k)$ 。

当 $k_{i, j}>k_{j, k}$ 时，如图：

显然，这时 $j$ 不可能成为最佳转移点。

而当 $k_{i, j} < k_{j, k}$ 时：

这时 $j$ 可能成为最佳转移点。

因此，对于所有可能成为最佳转移点的点构成的点集，其斜率必然单调递增。这就是一个凸壳。我们只需要维护这个凸壳，然后查找第一个相交的点即可。（第一个相交的点 $i$ 满足 $k_{i-1,i}<k\le k_{i, i+1}$ ）

现在问题变为了：如何维护这个凸壳？

这个问题很简单。只需要用一个单调队列，用类似找二维凸包的方式向外弹出斜率更大的队尾即可。

而题目中还有一个很好的条件： $t_i>0$ 。因此 $sumT$ 单调递增。我们在寻找相交的点时就可以不断从队头弹出无用决策（斜率小于当前的 $k$ ）。

这样就完成了，时间复杂度 $O(n)$ 。

加加强版

题意相同。

数据范围： $n\le 100000,-512\le t_i \le 512, 0<c_i\le 512$ 。

这时 $t_i$ 不满足单调递增的关系，我们无法每次从队头弹出元素，因为弹出的元素可能会成为以后的最佳转移点。因此我们需要维护整个凸包，在转移时，由于凸包上斜率单调递增，我们可以在单调队列里二分出第一个满足 $k_{i-1,i}<k\le k_{i, i+1}$ 的凸包上的点，它就是最佳转移点。时间复杂度会多一个 $\log n$ 。

加加加强版

$t_i, c_i$ 都可能为负数。

这时横坐标和斜率都无法满足单调递增关系，这就意味着我们无法用单调队列动态维护凸包（可能会在中间插入）。这时常见的有三种解决方案：

平衡树

平衡树可以做到在数列中动态加入数，这时我们可以在平衡树上二分查找最佳转移点。十分好理解，但是难写。

CDQ 分治

我们设 $\mathrm{CDQ}(l, r)$ 为计算 $[l, r]$ 这段区间的 $f$ 值。我们先递归计算 $\mathrm{CDQ}(l, mid)$ 。这时假设我们已经计算完了左半边，考虑左半边对右半边的贡献。我们可以将 $[l, mid]$ 的点组成的凸包建出来，因为这一部分已经计算完毕了，所以我们可以直接排序建凸包。

而对于右区间 $[mid + 1,r]$ ，我们也可以进行按斜率排序处理，这样就可以按照斜率单调递增的做法来弹出队头转移。最后再递归处理右区间 $\mathrm{CDQ}(mid + 1, r)$ 。

注意：处理右区间时不要将右区间的点加入凸包，因为我们计算的只是左区间对右区间的贡献，其余的贡献会继续递归处理。

李超线段树

我们可以再把转移方程搬过来：

f[i]-sumT[i]\times sumC[i]-s\times sumC[n]=\min _{j<i}\{f[j]-(sumT[i]+s)\times sumC[j]) \}

这时我们不按照上面的设法，我们重新理解下这个式子。

我们可以理解为有 $i-1$ 条直线 $1\sim i-1$ ，每条直线的斜率为 $-sumC[j]$ ，截距为 $f[j]$ ，而我们要查询当 $x=sumT[i]+s$ 时的最值。这个可以直接用李超线段树维护。

习题

Cats Transport

有 $m$ 只猫子， $p$ 只铲屎官。有 $n$ 座山，第 $i$ 座山与第 $i-1$ 座山的距离为 $D_i$ 。这些猫子都去玩，猫子 $i$ 去第 $H_i$ 座山玩，在 $T_i$ 时间结束游玩，然后在 $H_i$ 傻等铲屎官来接它。铲屎官必须把所有猫子都带上，每个铲屎官以每秒 $1$ 的速度不间断的从 $H_1$ 走到 $H_n$ 。每个铲屎官可以带上无限的猫子。现在安排每个铲屎官的出发时间（可以为负数），最小化猫子们的等待时间之和。求出最小等待时间之和。

数据范围： $m\le 100000, p\le 100$ 。

我们先设 $A_i=T_i-\sum_{i=2}^{H_i}D_i$ ，即猫子能被接到的最早出发时间。因此如果铲屎官从 $t$ 时刻出发，则这只猫子等待时间则为 $t-A_i$ 。

我们将 $A_i$ 排序，设 $s$ 为其排好序后的前缀和。利用临项交换法可以证明，一个铲屎官出发后带走的猫子在 $A$ 中一定是连续的一段。这时我们就可以把问题转化为上面的任务安排。

我们考虑一只铲屎官带走 $[l, r]$ 这些猫的代价为：

\sum\limits _{i=l}^{r}(A_r-A_i)=(r-l+1)A_r-s_r+s_{l-1}

我们设 $f[i][j]$ 为前 $i$ 只铲屎官带走了前 $j$ 只猫子，则转移方程为：

f[i][j]=\min_{k<j}\{f[i-1][k]+(j-k)A_j-s_j+s_k \}

这样复杂度为 $O(m^2p)$ 的，考虑斜率优化。

我们化简式子，能得到 $f[i][j]+s_j-j\times A_j=\min_{k<j}\{f[i-1][k]+s_k-A_j\times k\}$ 。这样就可以直接斜率优化了。

另外，本题可以加强数据到 $p\le 100000$ 。这时我们可以用 wqs 二分来消去 $i$ 这一维，使得时间复杂度降为 $O(m\log p)$ 。这里不再介绍。

Building Bridges

有 $n$ 根柱子依次排列，每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$ 。

现在想要建造若干座桥，如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间，那么需要 $(h_i-h_j)^2$ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$ ，注意 $w_i$ 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

数据范围： $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$ 。

本题很容易设出状态并写出转移方程： $f_i$ 表示 $1\sim i$ 建桥的代价，则

\begin{aligned} f_i & = \min _{j<i}\{f_j+(h_i-h_j)^2+sum_{i-1}-sum_{j} \}\\ &=\min _{j<i}\{f_j-sum_{j}+h_j^2-2h_i\times h_j \}+sum_{i-1}+h_i^2 \end{aligned}

这样就化为了斜率优化的形式，由于本题横坐标和斜率都不单调，则需要李超线段树或者 cdq 分治来优化。

斜率优化dp学习笔记

前置知识

斜率优化

习题

Cats Transport

Building Bridges

The End