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

会员专享

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

开通会员

思路

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

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析