hrbust 1788

按照开始时间做排序，不断更新在他之前的最大值，借此得出当前数据结束时间所能等到的最大值。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 struct po
 6 {
 7     int s,e,p;
 8 } a[100010];
 9 int cmp(po a,po b)
10 {
11     return a.s<b.s;
12 }
13 int maxsum[1000050];
14 int main()
15 {
16     int n;
17     while(scanf("%d",&n)!=EOF)
18     {
19         int maxd=0,i,j;
20         for(i=0;i<n;i++)
21         {
22             scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].p);
23             if(a[i].e>maxd)
24             maxd=a[i].e;
25         }
26         sort(a,a+n,cmp);
27         memset(maxsum,0,sizeof(maxsum));
28         for(i=0;i<n;i++)
29         {
30             if(i>0)
31             for( j=a[i-1].s;j<a[i].s;j++)
32             if(maxsum[j-1]>maxsum[j])
33             maxsum[j]=maxsum[j-1];
34             if(maxsum[a[i].s-1]+a[i].p>maxsum[a[i].e])
35             maxsum[a[i].e]=maxsum[a[i].s-1]+a[i].p;
36         }
37         int maxn=0;
38         for(int i=a[n-1].s;i<=maxd;i++)
39         {
40             if(maxsum[i]>maxn)
41         maxn=maxsum[i];
42         }
43         printf("%d
",maxn);
44     }
45     return 0;
46 }