斜率优化

斜率优化

说明(本文中所有的单调递增递减都不是绝对的，根据实际情况灵活使用)

对于形如(f[i]=max){(f[j]+a[i]+b[i]*c[j])}的状态转移方程，若(b[i])是单调递增的(可以是递减，但维护方式就不同了，下面不再说明)，那么我们可以对决策进行斜率优化。

证明

显然，对于两个决策(j和k(j<k)),决策(k)要优于决策(j)当且仅当

[f[j]+a[i]+b[i]*c[j]leq f[k]+a[i]+b[i]*c[k] ]

移项后

[b[i]*(c[j]-c[k]) leq f[k]-f[j] ]

除过去

[-b[i] leq frac{f[k]-f[j]}{c[k]-c[j]} ]

所以若(-b[i] leq frac{f[k]-f[j]}{c[k]-c[j]}),那么本次决策中决策(k)优于决策(j)
(之后所说的斜率均为(frac{f[k]-f[j]}{c[k]-c[j]}))((k>j))

维护

删除

对于这个我们可以用一个单调队列来维护一个单调递减的斜率。
因为(b[i])是单调递增的，所以若决策(k)在一次决策中要优于决策(j)，那么之后的所有决策中决策(k)都是要优于决策(j)的，这时我们就可以把决策(j)丢出单调队列

插入

插入一个决策时，由于我们要让斜率满足单调递减，所以若之前的斜率要小于现在的斜率，那么当前面那个斜率被删除后，这个斜率也一定会被删除，也就是说之前队尾的就决策没有用了，直接删除就好(若不删除，可能出现三个决策(a,b,c,决策a优于决策)b(但决策c优于决策a,但是由于决策b的阻隔，妨碍了决策c的使用))。

这样一来，我们每次只需选择队首的决策即可。
然后每个决策最多被插入和删除一次，所以时间复杂度是线性的，一般都能将(O(n^2)的转移优化成O(n))

斜率优化的方法大概就是这样，还是需要灵活运用。