3576068_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m, r;
struct Interval
{
	int st, ed, e;
	
	bool operator < (const Interval &that)	const
	{
		return st < that.st;
	}
}interval[1000];
int best[1000];

int main()
{
	int i, j;

	scanf("%d%d%d", &n, &m, &r);
	n += r;
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d", &interval[i].st, &interval[i].ed, &interval[i].e);
		interval[i].ed += r;
	}
	best[0] = interval[0].e;
	for (i = 1; i < m; i++)
	{
		j = i - 1;
		best[j] = interval[i].e;
		while (j >= 0 && interval[j].ed > interval[i].st)
		{
			best[i] = max(best[i], best[j]);
			j--;
		}
		best[i] = max(best[i], best[j] + interval[i].e);
	}
	printf("%d\n", best[m - 1]);
	return 0;
}