pku1201.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 71 行

#include <stdio.h>
#define TheMax 1000000
#define size 500001

typedef struct Node
{
	int s, e, m;
} Node;

Node d[size];
int v[size];
int min, max;
int N;

int main()
{
	int i, fd, k;
	scanf("%d", &N);
	min = TheMax;
	max = 0;
	for (i = 0; i < N; i++)
	{
		scanf("%d %d %d", &d[i].s, &d[i].e, &d[i].m);
		d[i].e++;
		if (min > d[i].s)
		{
			min = d[i].s;
		}
		if (max < d[i].e)
		{
			max = d[i].e;
		}
	}
	fd = 0;
	for (i = min; i <= max; i++)
	{
		v[i] = -TheMax;
	}
	v[min] = 0;
	for (k = min; !fd && k <= max; k++)
	{
		fd = 1;
		for (i = 0; i < N; i++)
		{
			if (v[d[i].s] != -TheMax && v[d[i].s] + d[i].m > v[d[i].e])
			{
				v[d[i].e] = v[d[i].s] + d[i].m;
				fd = 0;
			}
		}
		for (i = min; i < max; i++)
		{
			if (v[i] != -TheMax && v[i] > v[i + 1])
			{
				v[i + 1] = v[i];
				fd = 0;
			}
		}
		for (i = max; i > min; i--)
		{
			if (v[i] != -TheMax && v[i] - 1 > v[i - 1])
			{
				v[i - 1] = v[i] - 1;
				fd = 0;
			}
		}
	}
	printf("%d\n", v[max]);
	return 0;
}