【CodeVS 3027 线段覆盖2】

题目描述 Description

数轴上有n条线段,线段的两端都是整数坐标,坐标范围在0~1000000,每条线段有一个价值,请从n条线段中挑出若干条线段,使得这些线段两两不覆盖(端点可以重合)且线段价值之和最大。

n<=1000

输入描述 Input Description

第一行一个整数n,表示有多少条线段。

接下来n行每行三个整数, ai bi ci,分别代表第i条线段的左端点ai,右端点bi(保证左端点<右端点)和价值ci。

输出描述 Output Description

输出能够获得的最大价值

样例输入 Sample Input

3

1 2 1

2 3 2

1 3 4

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

数据范围

对于40%的数据,n≤10;

对于100%的数据,n≤1000;

0<=ai,bi<=1000000

0<=ci<=1000000

序列型动态规划,枚举每条线段,看它能够继承的最大值是多少,最后求一遍每条线段的最大值输出即可。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*