Doremy 的干燥计划题解

思路

扫描城市。对位置 $x$，记覆盖它的降雨日集合为 $A_x$。若 $A_x$ 为空，该城市天然干燥；若 $|A_x|>k$，无论如何都不能让它干燥；其余位置要变干燥，必须把 $A_x$ 的所有日子都选入取消集合。

因此问题变成：从 $m$ 个区间中选 $k$ 个，使满足 $A_x$ 为所选集合子集的位置尽量多。区间结构使相邻位置的集合只在端点处变化，也使扫描时可以按活动区间的左端点建立动态规划。

做法

把没有活动区间的位置数量单独计入答案。活动区间超过 $k$ 个的位置不能贡献。其余位置把活动区间按左端点从大到小排序，并把相同左端点合并处理。

维护 $dp[g][p]$：扫描到当前城市之前，使用 $g$ 个被取消的降雨日，并以边界 $p$ 作为上一段结束位置时，最多能获得多少个非天然干燥城市。对固定的 $g$，需要支持历史位置区间最大值查询和当前位置单点取最大更新。

若当前活动区间的最大左端点为 $q$，从边界 $p\in[q,x-1]$ 转移时不需要新选降雨日。继续枚举排序后的活动区间组；当已经纳入前 $j+1$ 个活动区间时，允许的旧边界形成一个由相邻左端点确定的连续区间，使用的日数增加 $j+1$。在对应的旧层区间最大值上加一，即得到让当前城市干燥的转移。

由于 $k\le10$，每个位置只有 $O(k^2)$ 次查询。用在线稀疏表维护每层的历史最大值，可在 $O(1)$ 时间查询；单点加入需要 $O(\log n)$。天然干燥城市最终统一加回。

第一档直接枚举所有大小为 $k$ 的取消集合。对于 $k=2$，只需统计仅被一天覆盖的城市数以及恰被一对天覆盖的城市数，再枚举实际出现过的二元组并结合最大的两个单日贡献。

正确性证明

城市 $x$ 干燥当且仅当覆盖它的每个降雨日都被取消，即 $A_x$ 是所选 $k$ 天的子集。因此空集合位置必然贡献，大小超过 $k$ 的集合必然不贡献。

扫描到位置 $x$ 时，所有可能影响它的日子正是活动区间。把它们按左端点降序排列后，旧边界 $p$ 落在两个相邻左端点之间，当且仅当恰有一个确定的活动区间前缀是在 $p$ 之后新出现、必须新加入取消集合。故每个旧状态落入唯一的查询区间，增加的日数也唯一；算法枚举全部组，既不会遗漏可行选择，也不会重复赋予错误的新增日数。

每次转移只从更早边界的合法状态出发，并在包含当前全部必要活动日时把贡献加一，所以所有生成状态都对应真实取消集合。反过来，任意固定的取消集合沿城市顺序产生的每次边界变化，都属于上述某个相邻左端点区间，因此其所有干燥城市都会被动态规划复现。取所有状态最大值并加上天然干燥城市数即为最优答案。

复杂度

满分做法的时间复杂度为 $O((n+m)\log m+n k^2)$，空间复杂度为 $O(nk\log n+m)$。