DP总结(四，斜率优化DP)

0.适用场景#

转移式形如 $dp _ i = a _ i b _ j + c _ i + d _ j$ 的 DP 就可以使用斜率优化，因为 $a _ i b _ j$ 这一项，单调队列优化不再适用。

1.原理#

设有转移方程 $dp _ i = \min _ {j \lt i} \{ dp _ j + (sum _ i - sum _ j + i - j - 1 - L) ^ 2 \}$，时间复杂度为 $\Omicron(n ^ 2)$，考虑优化。

先设 $S _ i = sum _ i + 1,l = L + 1$，为方便，我们先省去 $\min$ 的上下界，则有：

这个时候我们联想一次函数的解析式 $y = kx + b$，变形得到 $b = y - kx$，如果我们把每一个都看作变量，则 $kx$ 是一个二元函数，这启发我们将和 $i,j$ 同时相关的设为 $kx$，只和一个变量相关的看作 $y,b$，一般我们设需要取最值的为 $b$，也就是只与 $i$ 相关的设为 $b$，则只和 $j$ 相关的设为 $y$。

又因为我们需要已知斜率，所以 $k$ 为二次项中与 $i$ 相关的，$x$ 为二次项中与 $j$ 相关的。并且，解析式为 $b = y - kx$，所以一般 $k$ 值需要取负。

在本题中，我们可以做如下变量代换：

我们再将 $(x,y)$ 看作平面上的一个点，则题目转化为已知 $k _ i$，求最小的 $x _ j,y _ j$，使得 $b _ i$ 最小。

借用 OI-Wiki 的一张图：

可以发现，我们要做的就是沿着 $y$ 轴从下向上平移这条直线，使得第一个 $(x _ j,y _ j)$ 在该条直线上，这时 $b _ i$ 最小。同时，我们需要维护先前的决策点点集，并且我们发现，这个点集构成一个凸包，分如下情况讨论：

1.斜率与横坐标均单调#

我们维护一个队列 $Q$，使得 $\forall i \in (head,tail),\text{Slope}(Q _ {i - 1},Q _ i) \lt \text{Slope}(Q _ i,Q _ {i + 1})$，这里的 $\text{Slope}$ 表示斜率。

当我们找答案的时候，就是找到一个点 $p$，使得 $\text{Slope}(Q _ {p - 1},Q _ p) \le k \lt \text{Slope}(Q _ p,Q _ {p + 1})$，此时，点 $Q _ p$ 就为最优决策点。

我们查询完答案后，我们首先要维护斜率的单调性，我们要使 $\text{Slope}(Q _ {tail - 1},Q _ {tail}) \lt \text{Slope}(Q _ {tail},i)$，弹出所有不满足的 $Q _ {tail}$，再插入这个点，就好了。

2.有不单调的#

这个时候就不满足单调队列的性质了，我们可以采取以下方法来维护这个凸包

弹队首变为找到一个最小的 $p$ 使得上面的式子成立，可以用二分实现。

对于插入操作就不那么好维护了，我们可以使用两种方法维护这个凸包：

(1) 平衡树#

我们直接用平衡树来维护这个凸包，上面的二分操作就可以在平衡树上二分了。

可以不用手写，直接用 set 就行

(2) CDQ 分治#

我不会，看 OI-Wiki 得了

2.更高阶的#

我们发现，其实我们没必要对式子变形。

我们重新看原来的方程：

发现，我们的瓶颈就是在求 $\min$ 里面的式子。

我们沿用一次函数的模型来解决。但这次，我们的变量代换就不太一样了。

我们沿用二次项是与 $i,j$ 都有关的思路，但是，我们考虑代入求值。则与 $i$ 有关的是已知的，设为 $x$，与 $j$ 有关的设为 $j$，$\min$ 中只与 $j$ 有关的设为 $b$，则变量代换如下：

则问题转变为求一些一次函数在 $x = S _ i$ 处的极值，同时支持插入线段，这个可以用李超线段树来方便的维护。

并且代码比平衡树与 CDQ 分治短得多