考研清华2011复试机考第三题

题目描述

在某条线路上有N个火车站，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3.其对应关系如下:
距离s           票价
0<S<=L1         C1
L1<S<=L2        C2
L2<S<=L3        C3
输入保证0<L1<L2<L3<10^9,0<C1<C2<C3<10^9。
每两个站之间的距离不超过L3。
当乘客要移动的两个站的距离大于L3的时候，可以选择从中间一个站下车，然后买票再上车，所以乘客整个过程中至少会买两张票。
现在给你一个 L1，L2，L3，C1，C2,C3。然后是A B的值，其分别为乘客旅程的起始站和终点站。
然后输入N，N为该线路上的总的火车站数目，然后输入N-1个整数，分别代表从该线路上的第一个站，到第2个站，第3个站，……，第N个站的距离。
根据输入，输出乘客从A到B站的最小花费。
输入
以如下格式输入数据：
L1  L2  L3  C1  C2  C3
A  B
N
a[2]
a[3]
……
a[N]
输出
可能有多组测试数据，对于每一组数据，
根据输入，输出乘客从A到B站的最小花费。
样例输入
1 2 3 1 2 3
1 2
2
2
样例输出
2

#include <iostream>
#include <stdio.h>
#define MAX_N 1001
#define INF 9999999999
using namespace std;

int n;
long long dp[MAX_N][MAX_N];
long long l1,l2,l3,c1,c2,c3;
int a,b;
long long dist[MAX_N];



long long cost(int _a,int _b)
{
	long long d=dist[_b]-dist[_a];

	if(0==d)
		return 0;
	if(0<d && d<=l1)
		return c1;
	if(l1<d && d<=l2)
		return c2;
	if(l2<d && d<=l3)
		return c3;
	else
		return INF;	
}

long long dpit(int _a,int _b)
{
	long long min;
	if(dp[_a][_b])
		return dp[_a][_b];
	
	min=cost(_a,_b);
	for(int i=_a+1;i<_b;i++)
	{
		if(min>dpit(_a,i)+cost(i,_b))
			min=dpit(_a,i)+cost(i,_b);		
	}
	dp[_a][_b]=min;
	return min;
		
	
}

int main()
{

	int i,j;
	while(scanf("%lld%lld%lld%lld%lld%lld",&l1,&l2,&l3,&c1,&c2,&c3)==6)
	{
		cin>>a>>b;
		cin>>n;
		dist[1]=0;
		for(i=2;i<=n;i++)
		{
			scanf("%lld",&dist[i]);									
		}
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				dp[i][j]=0;	
		printf("%lld\n",dpit(a,b));

	}
		
	
	return 0;
}

注意：
有的测试数据比较大，简单的dp，注意用long long类型就好了，用scanf和printf，占位符用%lld，vc6.0里面没有long long，只有__int64，输入输出占位符用%I64d，注意提交的时候改过来就好了，题意没说l1,l2,l3,c1,c2,c3的数据类型，根据提交的代码分析，都是整数。