一类线段与点覆盖问题的总结
SkyWave
·
·
算法·理论
前言
感觉自己一直不太擅长这些问题，最近又遇到了好几道，像在提醒我有必要记一记了。
题目按照主算法分类，每类中的 题目按照我认为的 Codeforces 难度 Rating 排序。
所有题目都会上传到 Typical & Tricky Online Judge。
[持续更新中]
贪心
例 1
给定 n 条线段，每条线段覆盖一个闭区间 [l_i, r_i]。问最多选出多少条线段使得选出的任意两条线段都没有覆盖公共点。
### 解 1
将所有线段按右端点从小到大排序。记 $R$ 表示最后一条选择的线段的右端点，$ans $ 表示最终答案。初始 $R \gets 0, ans \gets 0$。从左往右依次考虑所有线段。若 $R < l_i$ 则执行 $R \gets r_i$，$ans \gets ans + 1$。
### 解 1 的正确性证明（解 2）
用一个别解来证明。
同样先将所有线段按照右端点从小到大排序。
记 $f_i$ 为考虑完前 $i - 1$ 条线段，第 $i$ 条线段必须选时最多能选多少条不相交的线段。
初始时 $\forall i \in \mathbb{N} : 1 \leq i \leq n, f_i \gets 1$。
主动转移和被动转移皆可，为了最后的形式和解 1 类似，我们选择主动转移。
```cpp
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (r[i] < l[j]) {
f[j] = max(f[j], f[i] + 1);
}
}
}
```
答案即为 $\max\limits_{1 \leq i \leq n}f_i$，这样实现时间复杂度为 $O(n^2)$。
事实上，每个 $f_i$ 转移给第一个 $r[i] < l[j]$ 的 $f_j$ 就已经足够了。因为 $r_i$ 单调不降，所以若 $i < k$，则 $f_i$ 能转移到的线段的集合一定是 $f_k$ 能转移到的线段的集合的超集。
有了这一事实，不难发现解 1 与解 2 形式上完全一致。
### 难度
1600
## 例 2