codevs3027线段覆盖2(DP)题解

题目描述 Description

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

n<=1000

输入描述 Input Description

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

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

输出描述 Output Description

输出能够获得的最大价值

样例输入 Sample Input

1 2 1

2 3 2

1 3 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

对于40%的数据，n≤10；

对于100%的数据，n≤1000；

0<=ai,bi<=1000000

0<=ci<=1000000

因为要求不覆盖，所以先把线段的右边点坐标排序一遍

其他就是dp求dp[i]最大值了，线段尾坐标>=线段头坐标就符合条件，跟普通dp一样

var
n,i,j,s,max,k,t,l:longint;
a,b,v,dp:array[1..1000] of longint;
begin
readln(n);
for i:=1 to n do read(a[i],b[i],v[i]);
for i:=1 to n do
for j:=1 to n-1 do
if b[j]>=b[j+1] then begin
t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t;
t:=b[j]; b[j]:=b[j+1]; b[j+1]:=t;
t:=v[j]; v[j]:=v[j+1]; v[j+1]:=t;
end;
dp[n]:=v[n];
for i:=n-1 downto 1 do begin
l:=dp[i];
for j:=i+1 to n do
if (b[i]<=a[j])and(l<=dp[j])
then l:=dp[j];
dp[i]:=l+v[i];
end;
max:=1;
for i:=1 to n do if dp[i]>max then
max:=dp[i];
writeln(max);
end.

By:AlenaNuna

codevs3027线段覆盖2(DP)题解

推荐阅读