pku2355.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10010
#define TheMax 1000000000
int L1, L2, L3, C1, C2, C3;
int Dis[SIZE], DP[SIZE];
int S, E;
int N;

int getprice(int x)
{
	if (x <= 0)
	{
		return 0;
	}
	if (x <= L1)
	{
		return C1;
	}
	if (x <= L2)
	{
		return C2;
	}
	if (x <= L3)
	{
		return C3;
	}
	return -1;
}

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

	scanf("%d%d%d%d%d%d", &L1, &L2, &L3, &C1, &C2, &C3);

	scanf("%d%d%d", &N, &S, &E);
	S--;
	E--;

	if (S > E)
	{
		tp = S;
		S = E;
		E = tp;
	}

	Dis[0] = 0;
	for (i = 1; i < N; i++)
	{
		scanf("%d", &Dis[i]);
	}
	for (i = 0; i <= N; i++)
	{
		DP[i] = TheMax;
	}
	DP[S] = 0;
	for (i = S + 1; i <= E; i++)
	{
		for (j = i - 1; j >= S; j--)
		{
			tp = getprice(Dis[i] - Dis[j]);
			if (tp < 0)
			{
				break;
			}
			tp += DP[j];
			if (tp < DP[i])
			{
				DP[i] = tp;
			}
		}
	}
	printf("%d\n", DP[E]);
	return 0;
}