斜率优化
__ryp__
·
·
个人记录
斜率优化可以优化这样的柿子：
f(i) = \max\limits_j f(j) - a_i a_j + b_j
在 i 转移时，若 j < k 比 k 优，那么
\begin{aligned}
& f(j) - a_ia_j + b_j \gt f(k)-a_ia_k+b_k \\
& f(j) + b_j - f(k) - b_k \gt a_i(a_j - a_k) \\
& \dfrac{f(j) + b_j - f(k) - b_k}{a_j-a_k} \gt a_i
\end{aligned}
我们将 (a_j, f(j) + b_j) 看作是一个点，那么就相当于这当直线 P_jP_k 的斜率大于 a_i 时，j 比 k 优。
这也就是一个下凸壳。我们用单调队列就可以维护。
注意到如果 a_i 单增，我们所切的斜率就单增，那么转移就可以做到均摊 O(1)。
如果要求的是最小值，那么当斜率小于 a_i 时 j 更优，于是我们就维护一个下凸壳，斜率是单调递减的，于是我们就要保证切的时候斜率也单调递减。
例题 P3648 [APIO2014] 序列分割
转移是显然的
\begin{aligned}
f(i, j) &= \max_{k=0}^{i-1} f(k, j - 1) +\sigma_{k} (\sigma_i - \sigma_k) \\
& = \max f(k, j - 1) - \sigma_k^2 + \sigma_k\sigma_i
\end{aligned}
这个转移是 O(n) 的。我们考虑怎么优化。
首先滚动掉第二维然后考虑。
每次用 $\sigma_i$ 去切即可。