撰写Bessie is such a hard-working cow. In fact, she is so focused on maximizing her productivity that she decides to schedule her next N (1 ≤ N ≤ 1,000,000) hours (conveniently labeled 0..N-1) so that she produces as much milk as possible.
Farmer John has a list of M (1 ≤ M ≤ 1,000) possibly overlapping intervals in which he is available for milking. Each interval i has a starting hour (0 ≤ starting_houri ≤ N), an ending hour (starting_houri < ending_houri ≤ N), and a corresponding efficiency (1 ≤ efficiencyi ≤ 1,000,000) which indicates how many gallons of milk that he can get out of Bessie in that interval. Farmer John starts and stops milking at the beginning of the starting hour and ending hour, respectively. When being milked, Bessie must be milked through an entire interval.
Even Bessie has her limitations, though. After being milked during any interval, she must rest R (1 ≤ R ≤ N) hours before she can start milking again. Given Farmer Johns list of intervals, determine the maximum amount of milk that Bessie can produce in the N hours.
Input
* Line 1: Three space-separated integers: N, M, and R
* Lines 2..M+1: Line i+1 describes FJ’s ith milking interval withthree space-separated integers: starting_houri , ending_houri , and efficiencyi
Output
* Line 1: The maximum number of gallons of milk that Bessie can product in the Nhours
Sample Input
12 4 2 1 2 8 10 12 19 3 6 24 7 10 31
Sample Output
43
题意：给出m个片段，求最大不重叠子片段和
题解：两种方法，一种是按照st排序，按照从前往后的方法，每次确定dp[i]的最大值。
另一种方法按照ed排序，以时间每次把i后面的dp[j]的值都等于dp[i]，每次向后覆盖。
第一种方法的复杂度为O(m^2),第二种方法复杂度为O(n*m),此题n>>m,所以只能用第一种方法。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e6+5;
int dp[maxn];
int n,m,r;
struct me{
int st;
int ed;
int v;
}ma[maxn];
bool cmp(me &a, me &b){
return a.st<b.st;
}
int main(){
scanf("%d%d%d", &n, &m, &r);
rep(i,1,m)scanf("%d%d%d", &ma[i].st,&ma[i].ed,&ma[i].v);
rep(i,1,m)ma[i].ed+=r;
sort(ma+1,ma+1+m,cmp);
int maxx=0;
rep(i,1,m){
dp[i]=ma[i].v;
rep(j,1,i-1){
if(ma[i].st>=ma[j].ed)dp[i]=max(dp[i],dp[j]+ma[i].v);
}
maxx=max(maxx,dp[i]);
}
printf("%d", maxx);
}
//未验证正确性
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e3+5;
int dp[maxn];
int n,m,r;
struct me{
int st;
int ed;
int v;
}ma[maxn];
bool cmp(me &a, me &b){
return a.ed<b.ed;
}
int main(){
scanf("%d%d%d", &n, &m, &r);
rep(i,1,m)scanf("%d%d%d", &ma[i].st,&ma[i].ed,&ma[i].v);
rep(i,1,m)ma[i].ed+=r;
sort(ma+1,ma+1+m,cmp);
int maxx=0;
rep(i,1,m){
dp[ma[i].ed]=max(dp[ma[i].ed],dp[ma[i].st]+ma[i].v);
maxx=max(maxx,dp[ma[i].ed]);
rep(j,ma[i].ed+1,n)dp[j]=dp[j-1];
}
printf("%d", maxx);
}