3576701_wa.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 51 行

#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 max(int a, int b)
{
	return a < b ? b : a;
}

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;
	}
	sort(interval, interval + m);
	best[0] = interval[0].e;
	for (i = 1; i < m; i++)
	{
		j = i - 1;
		best[i] = 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;
}