喂猫 题解

思路

设在时刻 $x$ 出现的猫数为 $c_x$，这些猫的出现区间左端点最小值为 $p_x$。如果在 $x$ 喂食，那么上一次喂食必须发生在 $p_x$ 之前；否则至少有一只同时覆盖两个喂食时刻的猫会被喂两次。

令 $dp_x$ 表示只考虑前 $x$ 个时刻时最多喂到的猫数。若不在 $x$ 喂食，答案为 $dp_{x-1}$；若在 $x$ 喂食，新增 $c_x$ 只猫，之前只能使用 $p_x-1$ 及以前的决策。因此

没有猫出现的时刻不需要喂食。

做法

子任务 1 枚举全部喂食时刻集合，逐只猫统计被覆盖次数，保留每只猫至多被覆盖一次的方案。

子任务 2 对每个时刻扫描全部区间，直接求 $c_x$ 与 $p_x$，再按转移式计算 DP。

完整做法用差分数组求所有 $c_x$。对相同左端点 $l$，只需记录最大的右端点 maxR[l]：当扫描到 $x$ 时，从当前指针开始跳过所有 maxR[l] < x 的左端点，停下的位置恰好是仍覆盖 $x$ 的区间中最小的左端点。指针只增不减，因此这一部分是线性的。

复杂度

子任务 1 的时间复杂度为 $O(2^n(n+m))$。子任务 2 的时间复杂度为 $O(nm)$。完整做法每组的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n)$。