关于斜率优化

今天我去复习斜率优化，然后看了半天书没看懂，然后去网上看了一篇博客，觉得 写得挺好的，然后还有了一点自己的理解，顾记此博客。

斜率优化是用于优化线性dp的，所以一般的线性dp都会涉及到最大最小值问题，然后就可以定义状态然后得出方程。

观察这个dp转移方程：

$f[i]=min_{j=1}^{i-1}(a[i]·x[j]+b[i]·y[j])$

注：$a,b,x,y$这四个数组是已知的

按照dp方程的描述，在更新$f[i]$时需要把1到i-1枚举一遍，所以算法的时间复杂度就是$O(n^2)$，所以必然会TLE。
但是我们发现了一件很有意思的东西，就是在更新$f[i]$时，$f[i]$的最终值只与j有关，就是在枚举$j=1$ $to$ $i-1$时，$i$是不变的，所以不难发现可能去更新$f[i]$的值只与$j$有关。
所以现在假设k是满足$f[i]$最小的$j$的值，然后记当$j=k$时（即$f[i]$的最小值)的$f[i]$为$↓f[i]$，所以就有等式：

$↓f[i]=a[i]·x(k)+b[i]·y(k)$

然后接下来求出k的过程类似于解方程，只不过知道的条件不一样而已。
先把这个式子变一个形：

$-b[i]·y(k)=-↓f[i]+a[i]·x(k)$

$y(k)=\frac{↓f[i]}{b[i]}-\frac{a[i]}{b[i]}·x(k)$

刚才提到了在更新$f[i]$时$i$是不变的，只有$j$在变，所以$a[i],b[i]$都是确定的，将其记为 $*C$
-带入原式：

$y(k)=\frac{↓f[i]}{*C}-\frac{*C}{*C}·x(k)$

有基础的数学概念的话就会发现一个常数对另外一个常数做运算得出的值也是常数，即：$*C$ ⊙ $*C$ = $*C$

注：⊙在此表示一种定义运算

由此可得$-\frac{*C}{*C}=*C$ -所以可得：

$y(k)=\frac{↓f[i]}{*C}+*C·x(k)$

所以要使f[i]最小，就要使$\frac{f[i]}{*C}$最小，即：

$↓f[i]$ 等价于 $↓\frac{f[i]}{*C}$

然后再看一遍$f[i]=min_{j=1}^{i-1}(a[i]·x[j]+b[i]·y[j])$
就很简单了，直接找到最合适 的 值即可