题解：P10784 【MX-J1-T4】『FLA - III』Wrestle

细数繁星 · 2025-10-23 20:58:06 · 题解

我竟然自己一个人把这道题切出来了（花了两天，只算零碎时间是 1 个小时）。算是考前给自己的信心。写完了还是有些感触的，故写篇题解祭。

先读题目。

因为是处理线段关系，所以不管三七二十一，先把蓝色线段按照 L_i 为关键字排序，红色线段按照 l_i 为关键字排序。

每个点至多被一个红色线段和一个蓝色线段覆盖。说明蓝色线段之间不会有交集，红色线段亦然。故 r_i<l_{i+1} 且 R_i<L_{i+1}。

定义 s_i 表示第 s_i 个红色线段为最左的和第 i 个蓝色线段有交集的线段，t_i 表示第 t_i 个红色线段为最右的和第 i 个蓝色线段有交集的线段。因为 L_i 的单调性且同色线段互不相交，所以可以通过二分求解 s_i 和 t_i。

选取线段是有代价的，即为有交的红色线段的权值。也是有收益的，即为交集长度。定义 v_i 为选取第 i 个蓝色线段的收益，c_i 为选取第 i 个蓝色线段的代价。根据题目，c_i=\sum\limits_{k=s_i}^{t_i} w_k。

而第 i 个蓝色线段选取的收益就比较复杂——要处理边际。如果有 l_{s_i}<L_i 和 r_{t_i}>R_i，则需要特殊处理。中间的皆为连续的，加上 \sum\limits_{k=s_i+1}^{t_i-1}r_k-l_k+1。

这两个求和，用前缀和优化。

再将 s,t,v,c 按照 s_i 排序。

而每个红色线段至多被一个蓝色线段覆盖。所以选取的蓝色线段的 [s_i,t_i] 不可以相交。

问题转化成了：有一些线段，代价为 c_i，收益为 v_i，起始点为 s_i，终止点为 t_i。求选取一些线段的最大收益，使得总代价不超过 k，且线段两两不相交（这里没有什么蓝色红色线段了）。

等等，这不就是 01 背包吗！

但因为不可以相交，所以方程为：

而这样的时间复杂度是 \mathcal{O}(m^2k)，只能拿 50 分。考虑优化。