dp - 斜率优化笔记

（原来的题解没得了，只好重写一份）

斜率优化一般是，\(dp\) 是枚举一个 \(i\)，然后前面找一个 \(j\)，式子中有些和 \(j\) 有关，有些和 \(i\) 有关，有些和俩都有关。

过程中，我们维护一个单调队列，它们可能作为最优的转移位置。其中队首是最优的，其它的是可能成为最优的（现在不是，可能以后）

核心步骤：把每个决策转化成平面直角坐标系上的点，然后从几何的角度考虑哪些点可能是最优的，哪些不可能。

我们发现这个性质好像很妙。所以说，不是所有题都可以斜率优化的。

这些说的肯定非常迷惑，看个实际的

最经典的入门题 HNOI2008玩具装箱

转移方程为 \(f_i=min(f_j+(s_i-s_j+i-j-L-1)^2)\)，非常 simple

我们令和 \(i\) 有关的为 \(a_i=s_i+i\)，和 \(j\) 有关的为 \(b_j=s_j+j+L+1\)

那 \(f_i=min(f_j+(a_i-b_j)^2)\)

拆开 \(f_i=min(f_j+a_i^2-2a_ib_j+b_j^2)\)

假设 \(j\) 是最优的那个转移，那

\(f_i=f_j+a_i^2-2a_ib_j+b_j^2\)

这个式子里面，注意到 \(2a_ib_j\) 这一项是同时与俩有关的。

我们把和 \(i\) 有关的那个 \(2a_i\) 看成斜率，和 \(j\) 有关的 \(b_j\) 看成 \(x\)。那 \(y\) 肯定也要和 \(j\) 有关，移到右边。我们的主体思想是把 \(f_i\) 变成一个截距。所以把 \(f_i\) 和一些只和 \(i\) 有关的东西放到左边。

（这一步就体现出“斜率”了）

变成 \(2a_ib_j+f_i-a_i^2=b_j^2+f_j\)。其中 \(x=b_j\)，\(y=b_j^2+f_j\)。

令 \(P_j\) 作为第 \(j\) 个决策点，坐标为 \((b_j,b_j^2+f_j)\)。

那现在问题转化成了：找到一个 \(j<i\)，使得过点 \(P_j\) 的斜率为 \(2a_i\)（定值）的直线的截距加上 \(a_i^2\)（定值）最小。

手画几张图可以得出以下结论：

然后就维护一个单调队列就完事了。复杂度是 \(O(n)\) 的，\(log\) 都不带。

巴特西