本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-21 09:27:14

斜率优化可以优化这样的柿子：

$$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$ 是非负序列的前缀和，其单增显然。于是我们可以按照上面的方式，设 $P_j(-\sigma_k, f(k) - \sigma_k^2)$。

每次用 $\sigma_i$ 去切即可。