题解

思路

把每个子数组看成带权集合，权值为区间和，要求选恰好 $k$ 个不同集合并覆盖全部位置。小规模可以直接枚举或按覆盖掩码做 0/1 DP；满分需要消去 $k$ 这一维。

做法

子任务 1

列出全部子数组，递归枚举选或不选，并记录已选数、覆盖掩码与总权值。恰选 $k$ 个且掩码覆盖全部位置时更新答案。

子任务 2

令 $dp[c][S]$ 表示处理若干不同区间后，选了 $c$ 个、覆盖集合为 $S$ 的最大总和。每个区间进行一次倒序 0/1 背包转移，答案为 $dp[k][2^n-1]$。

子任务 3

使用 WQS 二分。给每个被选区间减去罚值 $K$，先求覆盖全部位置时“调整后总和最大，若相同则区间数最多”的方案。随着 $K$ 增大，最优区间数单调不增；二分出仍能选择至少 $k$ 个区间的最大 $K$，再把 $kK$ 加回。

固定 $K$ 后按右端点扫描。所有调整后权值非负的区间必选；状态只需记录当前最左未覆盖位置。按前缀和排序，用两个树状数组维护当前右端点下非负区间的数量与总贡献；用线段树维护不同最左未覆盖位置的最优二元组，以及减去前缀最小值后的最优二元组，从而完成区间加和区间最大值转移。

复杂度

三档算法时间复杂度分别为 $O(2^{n(n+1)/2})$ 的受限枚举、$O(kn^2 2^n)$、$O(n\log^2 n\log V)$；满分算法空间复杂度为 $O(n)$，其中 $V$ 为答案斜率范围。

正确性说明

前两档分别完整枚举全部区间子集和标准 0/1 集合背包，因此不会重复选区间，且只接受覆盖全集的状态。满分算法中，对固定罚值，选择方案的目标变为原总和减去 $K$ 乘区间数；线段树 DP 精确枚举最左未覆盖位置的保持与被覆盖两类转移，并贪心加入所有非负区间。二元组第二关键字保证同值时取更多区间，使最优区间数关于 $K$ 单调。WQS 二分取临界罚值后加回 $kK$，由离散凸性得到恰选 $k$ 个区间的最优原总和。