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

當前沒有測試資料。

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库，可解锁完整内容。

开通会员

思路

动态规划 , 对线段中点 $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

编辑器加载中…

输入

预期输出（选填）