CF1442D Sum 做题记录

给定 $n$ 个单调不降的数组，初始计数器 $sum=0$。你需要进行 $k$ 次操作，每次选择某个数组的第一个未被删除的元素 $x$，将 $sum$ 加上 $x$，然后将 $x$ 从这个数组中删去。最大化 $sum$。

$1\le n,k\le 3000$，所有数组长度之和不超过 $10^6$，值域 $[0,10^8]$。

首先最多只有一个数组不是全选的，因为若存在两个数组 $a,b$ 不是全选，假设选择了 $a_{[1,x]}$ 和 $b_{[1,y]}$，则一定有 $a_{x+1}<b_y$，否则可以撤销 $y$ 选 $x+1$，那么由于 $a_x<a_{x+1},a_y<a_{y+1}$ 故一定有 $a_x<b_{y+1}$，所以此时撤销 $x$ 选 $y+1$ 是优的，矛盾。

那么问题变成了扣掉一个物品的 01 背包，这个是经典问题，可以做到 $O(nk\log n)$。具体的，考虑类似线段树一样分治，处理区间 $[l,r]$ 的时候先加入 $[l,mid]$ 中的物品，递归右半边；再撤销掉 $[l,mid]$ 中的物品（通过开桶记录加入前的状态实现），递归左半边。这样递归到单点的时候就求出了答案。

时间复杂度是 $T(n)=O(nk)+2T(\frac{n}{2})=O(nk\log n)$ 的。