算法学习笔记之斜率优化

本文主要是介绍算法学习笔记之斜率优化，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

近几日回归竞赛后，便开始学些新东西了（~~对于蒟蒻来说~~）。这几天就连续的更新一下自己对斜率优化的学习过程。

在一些常见的DP题中，可能会出现形如\(f[i]=\min/\max(f[j]+(sum[i]-sum[j])^2\)的转移方程式。
这时，我们就可以把后面的二次项展开：

\(f[i]=f[j]+sum[i]^2+sum[j]^2+2*sum[i]*sum[j]\)

\(f[j]+sum[j]^2=2*sum[i]*sum[j]+sum[i]^2+f[i]\)

再将\(2*sum[i]\)看做斜率，\(f[j]+sum[j]\)看做\(y\)，\(sum[j]\)看做\(x\)，则\(f[i]+sum[i]^2\)就成了截距，由于斜率不变，我们就用一个单调队列来维护之前的决策点，再将该斜率的直线从下到上平移，找到斜率最小的点。所以我们既要维护一个下凸包。

利用单调队列维护当前的决策点构成的凸包，在遍历到\(i\)时，先将斜率小于当前斜率的决策点全部删去。然后对头的点就是当前的最优决策点，更新当前值后，在队尾加点时保证斜率的单调递增即可。

这篇关于算法学习笔记之斜率优化的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！