Sum 题解

思路

令 $P_i(x)$ 表示从第 $i$ 个序列取前 $x$ 个数的和。由于原序列不降，$P_i$ 的相邻差分不降，所以它是离散凸函数。

固定总选取数为 $k$。若某个方案中有两个序列都只取了非空且非完整的前缀，那么可以在这两个序列之间不断转移一个选取名额。两个序列的总收益关于转移量仍然是凸函数，区间最大值一定在端点取得。因而总能把其中一个序列变成空序列或完整序列而不降低答案。重复此过程可知：存在最优方案，其中至多一个序列只取部分前缀，其余序列要么不取，要么整段取完。

这给出三层算法。

1. 小规模直接做分组背包。依次处理每个序列，枚举从该序列取多少个前缀元素，复杂度与所有可选前缀数成正比。
2. 中等规模枚举唯一可能的部分序列。对其余序列只保留“不取”和“整段取完”两个选择，做一次 0/1 背包后枚举该特殊序列的前缀长度。
3. 满分算法用分治消除重复背包。递归处理区间 $[l,r]$ 时，维护区间外所有序列作为完整物品的背包。进入左儿子前，把右半区所有完整物品加入背包；进入右儿子时反之。到达叶子 $i$ 后，背包恰好包含除 $i$ 外所有序列的完整选择，再枚举 $i$ 的前缀长度即可。

做法

背包数组 $dp[j]$ 表示从当前允许整取的序列中恰好选择 $j$ 个数所能得到的最大和，不可达状态为负无穷。加入一个长度为 $t_i$、价值为 $P_i(t_i)$ 的完整序列时，从大到小更新：

分治函数接收区间及区间外背包。若当前是叶子 $i$，枚举 $0\le x\le\min(t_i,k)$，用

更新答案。否则分别把另一半的完整序列加入背包副本后递归。每一层每个序列至多作为完整物品加入一次，分治共 $O(\log n)$ 层。

使用 64 位整数保存答案，因为最大和可达 $3\times10^{11}$。

复杂度

小规模分组背包的时间复杂度为 $O(k\sum_i\min(t_i,k))$，空间复杂度为 $O(k)$。

枚举部分序列算法的时间复杂度为 $O(n^2k+nk)$，空间复杂度为 $O(k)$。

分治满分算法的时间复杂度为 $O(nk\log n+nk)$，空间复杂度为 $O(k\log n+\sum_i\min(t_i,k))$。