译 By CmYkRgB123

描述

贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时，标记为0..N-1。

Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 <结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。

但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 R (1 ≤ R ≤ N) 个小时才能下次挤奶。给定Farmer John 计划的时间段，请你算出在 N 个小时内，最大的挤奶的量。

输入

• 第 1 行: 三个整数 N, M, R
• 第 2..M+1 行: 第 i+1 行 每行三个整数，为Farmer John挤奶计划的开始时间，结束时间，产量。

输出

• 第 1 行:一个整数 在 N 个小时内，最大的挤奶的量.

样例输入

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

样例输出

43

dp

读取数据时从1开始，排序却忘记+1。。。。。

#include 
#include 
#include 

using namespace std;

#define MAX_M 10000
#define MAX_N 1000001

struct TIMEQ
{
	int s,t;
	int val;
} TimeQ[MAX_M];
int N,M,R;
int dp[MAX_M];

int cmp(const void *a,const void *b)
{
	TIMEQ *pa,*pb;

	pa=(TIMEQ *)a;
	pb=(TIMEQ *)b;

	return pa->t-pb->t;
}

int main()
{
	freopen("milkprod.in","r",stdin);
	freopen("milkprod.out","w",stdout);

	scanf("%d%d%d",&N,&M,&R);

	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&TimeQ[i].s,&TimeQ[i].t,&TimeQ[i].val);
	}

	qsort(TimeQ,M+1,sizeof(TIMEQ),cmp);

	for(int i=1;i<=M;i++)
	{
		dp[i]=dp[i-1];
		for(int j=1;j