自动搬运

查看原文

来自洛谷，原作者为

	yzy1 Меня мое сердце, в тревожную даль зовёт.

搬运于2025-08-24 22:16:23，当前版本为作者最后更新于2023-05-25 07:37:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先考虑朴素做法：设 $\operatorname{dp}(i,j)$ 为将前 $i$ 个测试点分成 $j$ 个子任务的最小分数，则有转移

$$\operatorname{dp}(i,j) \gets \min_{k=0}^{i-1} \operatorname{dp}(k,j-1) + \operatorname{cnt}(k+1,i) (\textstyle \sum a_{[k+1,i]}). $$

其中 $\operatorname{cnt}(l,r)$ 表示假设以 $[l,r]$ 区间内的测试点作为一个子任务，能通过该子任务的人数．

朴素做法的时间复杂度是 $O(nm + m^2S)$，考虑对其优化．观察到我们没有利用 $n\le 50$ 的性质．考虑到

$$\begin{aligned} \operatorname{dp}(i,j) &\gets \min_{k=0}^{i-1} \operatorname{dp}(k,j-1) + \operatorname{cnt}(k+1,i) \textstyle \sum a_{[k+1,i]}\\ &= \min_{k=0}^{i-1} \fcolorbox{#f66}{#fee}{$\operatorname{dp}(k,j-1) + \operatorname{cnt}(k+1,i) \textstyle \sum a_{[k+1,n]}$} - \operatorname{cnt}(k+1,i) \textstyle \sum a_{[i+1,n]}. \end{aligned} $$

观察到其中的 $\operatorname{cnt}(k+1,i)$ 最大值为 $n$，且该式子的红色部分的值不随 $i$ 变化．我们可以维护 $n+1$ 个双指针，第 $i+1$ 个双指针维护满足 $\operatorname{cnt}(l,r)=i$ 的极大区间，很显然这样的区间唯一．同时每个双指针维护 $S$ 个堆表示这段区间内 $j$ 取不同值的时候上式红色部分的值．我们可以在枚举 $i$ 的时候去移动这 $n+1$ 个双指针，然后直接暴力查询这些双指针对应的堆里的最小值来更新 $\operatorname{dp}(i,j)$ 即可．由于每个双指针都只会移动 $O(m)$ 次，所以该做法的时间复杂度为 $O(nmS \log m)$．

更近一步地，显然每个双指针的左右两个指针都只会向右单向移动．我们可以用一个单调队列来代替堆．时间复杂度优化至 $O(nmS)$．

代码参考见 原始 OJ 提交．