首页 > ACM题库 > 九度OJ > 九度-1086-最小花费[解题代码]
2013
12-12

九度-1086-最小花费[解题代码]

题目来源: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

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main{	
	static long L[] = new long [3];
	static long P[] = new long [3];
	static int station[] ;
	static long dist[];
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextLong()){
			for(int i=0; i<6; i++){
				if(i>2)
					P[i-3] = s.nextLong();
				else
					L[i] = s.nextLong();
			}
			int a = s.nextInt()-1;
			int b = s.nextInt()-1;
			int n = s.nextInt();
			station = new int[n];
			dist = new long[b-a+1];
			for(int i=1; i<n; i++)
				station[i] = s.nextInt();
			f(a,b);
			if(b-a>0)
				System.out.println(dist[b-a]);
			if(b==a)
				System.out.println(0);
		}
	}
	static void f(int a,int b){
		for(int i=a+1; i<=b; i++){
			int count = 0;
			int x = i;
			while(x-count-1 >=a && station[x]-station[x-count-1] <= L[2])
				count ++;
			long min = Long.MAX_VALUE;
			for(int j=0; j<count; j++){
				min = Math.min(min,dist[i-j-1-a]+getP(station[i]-station[i-j-1]));
			}
			dist[i-a] = min;
		}
	}
	
	static long getP(long len){
		if(len == 0)
			return 0;
		else if(len <= L[0])
			return P[0];
		else if(len <= L[1])
			return P[1];
		else
			return P[2];
	}

}

/**************************************************************
	Problem: 1086
	User: coder
	Language: Java
	Result: Accepted
	Time:310 ms
	Memory:19792 kb
****************************************************************/


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience