P6001 题解

· · 题解

首先考虑朴素做法：设 \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 提交．