2022.9.21-互不重叠线段的最大价值

ID: 20

1000ms

256MiB

Difficulty: 5

No testdata at current.

思路

动态规划 , 对线段中点 $p$ 进行排序。从左往右 $n^2$ 的dp。

令 $dp_i$ 为以第 $i$ 条线段为最后一个线段的最大价值。我们 $O(n)$ 的考虑其他在第 $i$ 条线段前面的线段的 $dp$ 值，进行转移:

$$dp_i = max_{j=1}^{n} dp_j + w_i , 当 p_j + r_j <= p_i - r_i $$