bzoj1642 / P2889 [USACO07NOV]挤奶的时间Milking Time

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int max(int &a,int &b){return a>b?a:b;}
 7 struct data{
 8     int l,r,val;
 9     void Init(){scanf("%d%d%d",&l,&r,&val);}
10     bool operator < (const data &tmp) const{
11         return l<tmp.l;
12     } 
13 }a[1002];
14 int n,m,R,f[2000005];
15 int main(){
16     scanf("%d%d%d",&n,&m,&R);
17     for(int i=1;i<=m;++i) a[i].Init();
18     sort(a+1,a+m+1); int k=1;
19     for(int i=0;i<=n+R;++i){
20         if(i) f[i]=max(f[i],f[i-1]);
21         for(;a[k].l==i&&k<=m;++k)
22             f[a[k].r+R]=max(f[a[k].r+R],f[i]+a[k].val);
23     }printf("%d",f[n+R]);
24     return 0;
25 }