简单DP优化

Part 0. 引子

很多时候，我们一下想到的DP是 $\Theta(n^2)$ 级别的，但是题目的数据范围不允许。这个时候，我们就需要一定的方式来优化DP。

常见的DP优化很多，这里介绍单调队列优化和斜率优化。

Part 1. 单调队列优化

考虑形如下面形式的方程：

$dp[i]=\min_{i-k \le j \le i}\{c[j]\}+a[i]$

这里，请把 c[j] 当作一个关于 $j$ 的函数，比如 c[j]=dp[j]+a[j]

如果按照朴素算法进行计算，就是要两层循环，外层枚举 $i$，内层枚举 $j$，总复杂度为 $\Theta(n^2)$。

怎么优化呢？其实也很显然，就是如果在前面的计算中，发现有一个数，既比当前的值靠后，又比当前值小，那么当前值肯定不是最优的答案。也就是说我们完全可以搞一个单调队列，如果加入了一个值以后，破坏了其单调性，那么这个值肯定要优于前面的值，于是把队尾的元素弹出，直到满足单调性为止。代码也很简单。

这个算法能把时间复杂度从 $\Theta(n^2)$ 降到 $\Theta(n)$，使用的要求是能够使决策只与 $j$ 有关，与 $i$ 无关，否则就不能满足单调性了。

不明白？这里有个例子。

$dp[i]=\min_{1 \le j \le i}\{a[j]d[i]-dp[j]\}$

这个就不能用单调队列。可以很轻松地找到一些反例，这里就不举例了。

那咋办呢？

Part 2. 斜率（凸壳）优化

是啊，咋办呢？

我们去掉 $\min$，这样方便观察：

$dp[i]=a[j]d[i]-dp[j]$

再移项，得到：

$dp[j]=a[j]d[i]+dp[j]$

你看到了什么？如果你什么都没看出来，恭喜你，答对了。下面我们进行一下魔改：

令

$y=dp[j],k=d[i],x=a[j],b=dp[i]$

则有

$y=kx+b$

这回看懂了？没错，这是一个形如一次函数解析式的式子。注意，这里只是形如，因为这里的 $y$ 与 $x$ 都是关于 $j$ 的函数，并没有 $y$ 是关于 $x$ 的函数的关系。其中由于 $b$ 是 $dp[i]$，所以这个才是真正的变量，对于每一个 $j$，都有一个唯一的 $b$。

接下来，就要开始应用“斜率”了。

注意，本优化方式要求 $k,x$ 都是单增的。

第一步：求一个 $dp[i]$

先不管所有的 $b$，我们只求其中一个。

首先由于 $i$ 是固定的，$k$，也就是斜率，就是固定的了。

对于每一个 $j$，我们在平面直角坐标系上找到一个点 $P_j(x_j,y_j)$。这样，这个点一定在一条直线 $y=kx+b$ 上。

等会！刚才我们提到那个 $y=kx+b$ 不是解析式，怎么这里又变成直线了呢？因为这里的 $y,x$ 指的是坐标，也就是说这里的这两个字母的意义并不一样，并非通过换元得到。

好了，这样的话，我们要求的就是 $b$。但凡学过一次函数，我们就知道这个 $b$ 就是直线与 $y$ 轴的交点纵坐标。

来看看：

绿色的点表示 $P_j$。很明显，下面的线对应的 $b$ 是更小的。换句话说，就是用一条线向上扫，当扫到第一个点的时候就是最优答案。

我们观察这个图。其中，红线有用吗？并没有。

看这个图：

显然，这个红线在 $k$ 发生变化的时候，永远不会是最下方的点。因此，在我们添加新点的时候，如果发现这个新点和前面点的斜率比前面那条线段的斜率要小，那么前面这个点就是没有用的，因为 $k$ 小的时候这个点前面的点比他靠下，当 $k$ 变大的时候又变成了后面的点比他靠下，所以这个点就可以直接删除。

如果我们从左往右看，就会发现去掉这个点以后，连接所有点，就会形成一个下凸壳。这些点在 $i$ 变化的时候，不会发生变化。

仅仅从这个图来看，如果我们求现在的 $b$ 的最小值，那么就一定是 $j=2$ 的情况，也就是最靠下的那条线。

那么，考虑下凸壳，答案是什么呢？就是找到一个点 $P_j$，使得 $k_{P_{j-1}P_j} \le k_i \le k_{P_{j+1}P_j}$

在刚才考虑删除红线的时候，我们发现，这里的斜率……是单调的！那么我们是不是就可以用单调队列优化了？没毛病。我们利用单调队列存储当前的所有点 $P_j$。

在完成一次操作以后，我们就可以进入下一步了。

第二步：求所有 $dp[i]$

有了前面的铺垫，这一步还是比较好想到的。先考虑朴素的想法，那就是每一次都从头扫一遍 $P_j$，找到符合条件的。优化也显然，因为我们的 $k$ 单增，所以前面已经排除的 $P_j$ 一定不可能在后面再成为答案，也就是说，我们再利用单调队列的原理，把队头中已经判定完成的点都弹出即可。最终答案就是队头的点。

Part 4. 结语

这两个优化方式是比较好理解的。但是其实本文中并没有对一些结论进行证明（虽然他们都很“显然”），但是如果严谨证明一遍，在考场上能够更踏实地使用。

另外，如果你去洛谷上找题目，就会发现斜率优化的题都是蓝紫黑。不要心存畏惧，不就是斜率优化吗？DP 并不是什么难以理解的算法，所以这些题主要考察的是思维，只要能打通思路就比较好想。