题目大意

在坐标的x轴上有$n$条线段，第i条线段拥有$w_i$的价值。请问选出若干条互不重叠的线段的最大价值是多少？

题目大意

这道题目要求在坐标的x轴上选择若干条互不重叠的线段，使得所选线段的总价值最大

思路

每条线段由中点的横坐标、半径长度和价值决定。具体来说，线段的起点和终点分别为 p[i] - r[i] 和 p[i] + r[i]。选择的线段必须满足任意两条线段不重叠，即对于任意两条线段 i 和 j，要么 p[i] + r[i] <= p[j] - r[j]，要么 p[j] + r[j] <= p[i] - r[i]。 为了求解这个问题，我们可以采用动态规划的方法。以下是具体的步骤和分析：

1. 线段的表示与排序 首先，我们需要将每条线段表示为一个结构体，包含起点、终点和价值。然后，将所有线段按照结束位置（即 p[i] + r[i]）从小到大排序。这一步的目的是为了在后续的动态规划中，能够方便地找到不重叠的线段。