RainAir
My OI Blog
RainAir
「JZOJ6391」区间

题目链接

题解

一个我想不到的性质:每个点至多会被覆盖两次。
因为如果一个点被覆盖三次,那么肯定有一条线段的效果是可以被另外两条完全表达出来的,所以可以删去这个线段。
我们先将线段按照右端点排个序,有了这个性质,又因为它是个最优化问题,启发我们设 $f_{i,j}$ 表示考虑到了前 $i$ 个线段,最后一段被覆盖了一次的线段是 $[j,r_i]$ 的最小代价。答案就是所有 $r_i = n$ 的 $f_{i,*}$ 的最小值。
考虑转移:我们枚举上一条线段 $j$,如果 $r_j < l_i$ 那么显然不能转移(会留下空),但是我们也要注意如果 $j$ 是被 $i$ 完全包含的也不能从这里转移,因为会少算其它线段的影响(没错我一开始就挂了)。分类讨论:
1. $r_j + 1 = l_i$,所以 $[l_i,r_i]$ 没有被覆盖过,$f_{j,[1,r_i]}$ 和 $w_i$ 取 max。
2. $r_j \in [l_i,r_i)$,所以有一段被覆盖过,$f_{j,[1,l_i]}$ 和 $w_i+w_j$ 取 max。
直接转移是 $O(n^2m)$ 的,使用前缀和优化可以做到 $O(n^2+nm)$。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/934
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「JZOJ6391」区间
题目链接 题解 一个我想不到的性质:每个点至多会被覆盖两次。 因为如果一个点被覆盖三次,那么肯定有一条线段的效果是可以被另外两条完全表达出来的,所以可以删去这个线段。 我们先将…
扫描二维码继续阅读
2019-10-28
标签
近期评论