题解：CF425E Sereja and Sets

MX-C day1 T1。

### 题意

数轴上有 $n$ 个点，构成了 $\frac{n(n+1)}2$ 个线段。令所有线段为全集。问有多少子集，满足这个子集内的线段，在两两不交的情况下能选出的最多线段数恰好为 $k$。$k \le n \le 500$。

### 做法

如果暴力 dfs，那么 check 的做法是经典贪心。即将所有线段按照**右端点**排序，然后顺次判断能不能选这条线段。见 [AcWing 908.](https://www.acwing.com/problem/content/910/)。

数据范围不大，考虑狠狠地 DP。

设 $f(i, j)$ 表示当前贪心得到的最大右端点的位置 $\le i$，且最优策略中选择的线段数量为 $j$ 时的总方案数。

或者，$f(i, j)$ 即有多少个原题的答案的线段集合，使得这个集合的最优选择中最靠右的线段的右端点 $\le i$，且最优方案选择的线段数量为 $j$。

转移。枚举倒数第二大的最优选择中的线段的右端点 $p$。我们考虑线段 $[l, r]$（$l \le r \le i$）：

- 若 $r \le p$：那么这条线段在 $f(p, j - 1)$ 中已经被计算过了。
- 若 $l \le p$ 且 $p < r < i$：这条线段一定不在 $f(i, j)$ 的最优选择中。所以这样的线段可有可无，方案是 $2^{p (i-p-1)}$。
- 若 $p \le l < r < i$：这条线段如果存在，就不满足「最优选择中最靠右的线段的右端点为 $i$」这个条件。所以这样线段不能出现。
- 若 $l \le p$ 且 $r = i$：这条线段一定不在 $f(i, j)$ 的最优选择中。所以这样的线段可有可无，方案是 $2^p$。
- 若 $p < l$ 且 $r = i$：这条线段可能是 $f(i, j)$ 状态中所说的「最优选择中最靠右的线段的右端点为 $i$」的线段，但是这条线段只能有一条，而剩下的线段可有可无。方案是 $(2^{i-p} - 1)$。

综上转移：
$$
f(i, j) = \sum_{p=0}^{i-1} f(p,j-1)\times 2^{p(i-p-1)} \times 2^p \times (2^{i-p}-1)
$$
初始化：

- $f(i, 0)$：表示最优方案选择的线段数量为 $0$。显然只用空集一个，答案为 $1$。
- $f(0, i)$：表示线段右端点为 $0$。仍然只用空集一个，答案为 $1$。

快速幂是过不掉的。我们考虑预处理一些 $2$ 的幂：

- $2^p$，$2^{i-p}$：线性递推。
- $2^{p(i-p-1)}$：设 $g_{i, j} = 2^{ij}$，那么转移 $g_{i, j} = g_{i - 1, j} \times 2^j$ 或 $g_{i, j} = g_{i, j - 1} \times 2^i$。

正在渲染内容...