3027 线段覆盖 2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN=1001;
 6 struct node
 7 {
 8     int bg;
 9     int ed;
10     int v;
11 }a[MAXN];
12 int comp(const node &a ,const node &b)
13 {
14     return a.ed<b.ed;
15 }
16 int dp[MAXN];
17 int main()
18 {
19     int n;
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++)
22     {
23         int x,y,z;
24         scanf("%d%d%d",&x,&y,&z);
25         if(x>y)swap(x,y);
26         a[i].bg=x;a[i].ed=y;a[i].v=z;
27     }
28     sort(a+1,a+n+1,comp);
29     for(int i=1;i<=n;i++)
30     {
31         dp[i]=max(dp[i-1],a[i].v);
32         for(int p=i-1;p>=1;p--)
33         {
34             if(a[p].ed<=a[i].bg)
35             dp[i]=max(dp[i],dp[p]+a[i].v);
36         }
37     }
38     printf("%d",dp[n]);
39     return 0;
40 }