Yet Another Partiton Problem 题解

· · 个人记录

我们有一个基本转移。设 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 单不减。

我们可以简单分一下桃子

\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)。

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

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