3576772_ac_0ms_224k.cpp

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

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

using namespace std;

int n, m, r;
struct T
{
	int st, ed, e;
	
	bool operator < (const T &t)	const
	{
		return st < t.st;
	}
}itv[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", &itv[i].st, &itv[i].ed, &itv[i].e);
		itv[i].ed += r;
	}
	sort(itv, itv + m);
	int ans = best[0] = itv[0].e;
	for (i = 1; i < m; i++)
	{
		int tmp = 0;
		for (j = i - 1; j >= 0; j--)
		{
			if (itv[j].ed <= itv[i].st)
			{
				if (best[j] > tmp)
				{
					tmp = best[j];
				}
			}
		}
		best[i] = tmp + itv[i].e;
		if (best[i] > ans)
		{
			ans = best[i];
		}
	}
	return printf("%d\n", ans);
}