斜率优化DP

适用问题

对于某些DP式子，需要求出$i$之前的一些最小或最大值，如

$Dp[i] = min\{Dp[j]\} + ... (j < i)$

这样的式子中，取$min$运算里面的所有值只与$j$有关，因此可以用单调队列

但是某些DP式子形如

$Dp[i] = min\{Dp[j]+(sum[i+1]-sum[j])^2+M\}$

暴力转移复杂度为$O(n^2)$，而且式子中的$min$运算同时和$i,j$都有关，不可使用单调队列，可以考虑使用斜率优化将复杂度降到$O(n)$或者$O(nlogn)$

基本思想

Dp的过程无非是不断选取最优决策的过程，对于不优的决策，或者不可能成为最优的决策，我们都希望将它踢出来达到最优。

斜率优化的过程实际上是找到踢出不优决策条件的过程，并且这个条件必须只与两个决策有关，而不应该与$i$有关，比如说，某Dp式子推出的条件就是

$\frac{F_{k1}-F_{k2}}{S_{k1}-S_{k2}} < 2 * S_{i+1}$

左边部分的式子与$i$是无关的

一、基本过程(寻找决策条件)

1.找到原式子

以hdu3507题目为例，经过简单推导，得到的原始DP式子是这个样子

$dp[i]=min\{dp[j]+(sum[i+1]-sum[j])^2+M\}(j<i)$

2.假设两个可行的转移，并强制其中一个更优

在确定$i​$的情况下，设$T(x) = dp[x]+(sum[i+1]-sum[x])^2+M​$

比如我可以在这里假设两个可行的转移，$k_1<i,k_2<i$

强制从$k_2$转移过来比$k_1$转移过来更优，也就是$T(k_2)<T(k_1)$

带入$T(x)$中可以得到

$dp[k_2]+(sum[i+1]-sum[k_2])^2+M < dp[k_1]+(sum[i+1]-sum[k_1])^2+M$

3.化简式子，并主动将与i无关的量移到等式一边

将上面式子左右两边的$M$约掉，然后把平方打开，得到下列式子

$dp[k_2]+sum[i+1]^2+sum[k_2]^2-2sum[i+1]sum[k_2] < dp[k_1]+sum[i+1]^2+sum[k_1]^2-2sum[i+1]sum[k_1]$

左右有相同项$sum[i+1]^2$同时约去得

$dp[k_2]+sum[k_2]^2-2sum[i+1]sum[k_2] < dp[k_1]+sum[k_1]^2-2sum[i+1]sum[k_1]$

观察式子发现这个式子有一次项，也有二次项，有与i有关的量，也有与i无关的量

通常我们是先将一次项且与i无关的量先移到一边，再继续观察

上面式子移项就可以得到

$dp[k_2]-dp[k_1]+sum[k_2]^2-sum[k_1]^2 < 2sum[i+1](sum[k_2]-sum[k_1])$

右边还有一团与i无关的因子$sum[k_2]-sum[k_1]$，移到左边得

$\frac{dp[k_2]-dp[k_1]+sum[k_2]^2-sum[k_1]^2}{sum[k_2]-sum[k_1]}<2sum[i+1]$

现在左边完全只与你枚举的两个决策$k_1,k_2$有关，而右边只与当前计算的$dp[i]$的$i$有关

4.将与同一个决策有关的相关式子抽象成函数(换元)

$\frac{dp[k_2]-dp[k_1]+sum[k_2]^2-sum[k_1]^2}{sum[k_2]-sum[k_1]}<2sum[i+1]$

考虑到刚才化简的式子，左边得分子部分，与一个决策有关的量有$dp[x] 和 sum[x]^2$ 两项，可以换元来方便计算

比如令$T(x)=dp[x]+sum[x]^2$，那么式子就可以化为

$\frac{T(k_2)-T(k_1)}{sum[k_2]-sum[k_1]} < 2sum[i+1]$

然后对比一下数学平面直角坐标系中求两点$(x_1,y_1)(x_2,y_2)$连成的直线的斜率式子$k=\frac{y_2-y_1}{x_2-x_1}$

是不是非常相似，所以对于任意决策$k_2,k_1$，只要满足$\frac{T(k_2)-T(k_1)}{sum[k_2]-sum[k_1]} < 2sum[i+1]$，那么就一定满足我们第2步的强制假设$k_2$优于$k_1$

二、进阶过程(根据第一步得出条件踢出不优解)

未完待续