3576748_ac_0ms_224k.cpp

北大大牛代码 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;
	}
	sort(interval, interval + m);
	int ans;
	ans = best[0] = interval[0].e;
	for (i = 1; i < m; i++)
	{
		int tmp = 0;
		for (j = i - 1; j >= 0; j--)
		{
			if (interval[j].ed <= interval[i].st)
			{
				if (best[j] > tmp)
				{
					tmp = best[j];
				}
			}
		}
		best[i] = tmp + interval[i].e;
		if (best[i] > ans)
		{
			ans = best[i];
		}
	}
	printf("%d\n", ans);
	return 0;
}