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

我们有一个基本转移。设 $f(i, j)$ 代表前 $i$ 个数，分了 $j$ 组的最小权值，那么

$$f(i, j) = \min_{0\le k\lt i} f(k, j - 1) + (i - k) \times \max\limits_{l=k+1}^i a_l$$

这个 $\max$ 相当唐，我们用普通的想法很难把它去掉。

考虑跑 $k$ 轮分治，用类似 CDQ 的思想，以左区间去贡献右区间。

怎么合并？分治后，柿子里头的 $\max$ 就变成了一个前后缀最大值的 $\max$。

我们设 $\text{mid}$ 前的后缀最大值为 $p$，其后面的前缀最大值为 $q$，那么 $p$ 显然单不增，$q$ 单不减。

我们可以简单分一下桃子

• $q_i \ge p_j$

$$ \begin{aligned} f(i) &= g(j) + (i-j)q_i \ &= g(j) - q_ij + iq_i \end{aligned} $$

斜率优化显然，决策点是 $(j, g(j))$。为了快速维护 $q_i \ge p_j$ 的性质，我们用双指针（这也是 CDQ 标配），$i$ 从左向右，而 $j$ 从右向左，逐渐加入决策点并维护凸包性质。加入的斜率是单调递减的，于是成为一个上凸壳。我们要在这个上凸壳上找最小值，就要求每次头的斜率小于切的斜，发现

我们加入直线的顺序是单调递减的，那么

然后以均摊 $O(1)$ 复杂度更新 $f(i)$。

• $q_i \lt p_j$

$$ \begin{aligned} f(i) &= g(j) + (i - j) p_j \ &= g(j) + ip_j - jp_j \end{aligned} $$

决策点是 $(p_j, g(j) - jp_j)$，切的