4007909_wa.cpp

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

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

int n, k;

struct node
{
	int p, l, s;

	bool operator < (const node &t)	const
	{
		return s < t.s;
	}
}itv[100];

int best[16001];

int fmin(int a, int b)
{
	return a < b ? a : b;
}

int fmax(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int i, j, t;

	scanf("%d%d", &n, &k);
	for (i = 0; i < k; i++)
	{
		scanf("%d%d%d", &itv[i].l, &itv[i].p, &itv[i].s);
	}
	std::sort(itv, itv + k);
	for (i = itv[0].s; i <= n; i++)
	{
		best[i] = fmin(i, itv[0].l) * itv[0].p;
	}
	int ans = best[n];
	for (i = 1; i < k; i++)
	{
		int g = best[itv[i].s - 1];
		for (j = fmin(n, itv[i].s + itv[i].l - 1); j >= itv[i].s; j--)
		{
			t = j - itv[i].l - 1;
			if (t < 0)
			{
				best[j] = fmax(best[j], j * itv[i].p);
				continue;
			}
			best[j] = fmax(best[j], g + itv[i].l * itv[i].p);
			g = fmax(best[t], g - itv[i].p);
		}
		t = itv[i].s + itv[i].l - 1;
		for (j = t + 1; j <= n; j++)
		{
			best[j] = fmax(best[j], best[t]);
		}
		ans = fmax(ans, best[n]);
	}
	printf("%d\n", ans);
	return 0;
}