题目地址：http://ac.jobdu.com/problem.php?pid=1086
- 题目描述：
- 在某条线路上有N个火车站，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3.其对应关系如下:
距离s 票价0<S<=L1 C1L1<S<=L2 C2L2<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 C3A BNa[2]a[3]……a[N]
- 输出：
-
可能有多组测试数据，对于每一组数据，根据输入，输出乘客从A到B站的最小花费。
- 样例输入：
-
1 2 3 1 2 3
1 2
2
2
- 样例输出：
-
2
提交了五次终于AC了，有点激动啊！！！
#include <stdio.h> #define MAXC 2211686018427387904
#define MAXN 30000 long long l1, l2, l3, c1, c2, c3; //距离、花费
int N; //车站数 long long Compute_Cost(int start, int end, long long len[]);
long long getSpend(int start, int end, long long len[]); int main(void){
int start, end; //开始站、结束站
long long len[MAXN] = {0};
int i; while (~scanf("%lld %lld %lld %lld %lld %lld",&l1,&l2,&l3,&c1,&c2,&c3)){
scanf("%d %d", &start, &end);
scanf("%d", &N);
len[1] = 0;
for (i=2; i<=N; ++i){
scanf("%lld", &len[i]);
}
printf("%lld\n", Compute_Cost(start, end, len));
}
return 0;
} long long getSpend(int start, int end, long long len[]){
if (len[end] - len[start] <= l1)
return c1;
else if (len[end] - len[start] <= l2)
return c2;
else
return c3;
} long long Compute_Cost(int start, int end, long long len[]){
int i, j;
long long min, tmp;
long long cost[MAXN] = {0};
cost[start] = 0;
for (i=start+1; i<=end; ++i){
min = MAXC;
for (j=i-1; j>=start && (len[i]-len[j] <= l3); --j){
tmp = cost[j] + getSpend(j, i, len);
if (tmp < min)
min = tmp;
}
cost[i] = min;
}
min = cost[end];
return min;
}