题目描述：
在某条线路上有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<stdio.h>
#define MAXN 2211686018427387904
#define MAXS 30000
long long l1,l2,l3,c1,c2,c3,rout[MAXS];
long long spe(int start,int end)//输入起始点与终点的站号，输出这俩站之间的花费。
{
int temp=rout[end]-rout[start];
if(temp<=l1)return c1;
if(temp<=l2)return c2;
if(temp<=l3)return c3;
return MAXN;
}
int main()
{
long long temp,i,j,a,b,n,spend[MAXS];
while(~scanf("%lld %lld %lld %lld %lld %lld",&l1,&l2,&l3,&c1,&c2,&c3))
{
for(i=temp=0;i<MAXS;i++)rout[i]=spend[i]=MAXN;
scanf("%lld %lld",&a,&b);
scanf("%lld",&n);
rout[1]=0;
for(i=2;i<=n;i++)scanf("%lld",&rout[i]);
for(i=a,spend[a]=0;i<b;i++)
{
for(j=i+1;rout[j]-rout[i]<=l3&&j<MAXS;j++)//保证下面spe函数的输入俩站间距离是小于等于l3的。
{
temp=spe(i,j);
if(spend[j]>spend[i]+temp)spend[j]=spend[i]+temp;
}
}
printf("%lld\n",spend[b]);
}
return 0;
}
翻了说有一篇思路很好，虽然是java也复制一下
代码
package Test1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Test15_1086 {
/**
* by qr jobdu 1086 2014-8-12
* @throws IOException
*
* Accepted 70MS
*/
static long L1,L2,L3,C1,C2,C3;
public static void main(String[] args) throws IOException {
StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
while((st.nextToken())!=StreamTokenizer.TT_EOF){
L1=(long)st.nval; //long型
st.nextToken();
L2=(long)st.nval;
st.nextToken();
L3=(long)st.nval;
st.nextToken();
C1=(long)st.nval;
st.nextToken();
C2=(long)st.nval;
st.nextToken();
C3=(long)st.nval;
st.nextToken();
int A=(int)st.nval;
st.nextToken();
int B=(int)st.nval;
st.nextToken();
int N=(int)st.nval;
long a[]=new long[N+1]; //第一个站到第N个站的距离
a[1]=0;
for(int i=2;i<=N;i++){
st.nextToken();
a[i]=(int)st.nval;
}
//get the min cost
long disAB=a[B]-a[A];
if(B==A) //!!
System.out.println("0");
else if(disAB<=L1)
System.out.println(C1);
else if(disAB<=L2)
System.out.println(C2);
else if(disAB<=L3)
System.out.println(C3);
else{ //>L3 分段 动态规划思想
long mincost[]=new long[B-A+1]; //0号元素是A ，1号元素是A+1。。。。。B-A号元素是B ，i号元素代表A站到第i站的最小花费
// mincost[0]=0; // do not necessary 初始就是0
for(int i=A+1;i<=B;i++){ //每for循环一次确定到一个站的最小花费
int count=0;
while( count <= i-(A+1)&& a[i]-a[i-count-1] <= L3 ){ //计算本站前面不超过L3的站有几个 第i站到A站 第i站和第A站之间最多有(i-(A+1))个站
count++;
}
long min=Long.MAX_VALUE;
for(int j=0;j<count;j++){ //依次算出 到本站的最小花费。 实用动态规划的思想。 min为到第i站的最小花费
min=Math.min(min, mincost[i-(A+1)-j]+getCost(a[i]-a[i-j-1]));
}
mincost[i-A]=min;
}
System.out.println(mincost[B-A]);
}
}
}
static long getCost(long dis){
if(dis==0)
return 0;
else if(dis<=L1)
return C1;
else if(dis<=L2)
return C2;
else
return C3;
}
}
思路
http://www.cnblogs.com/love533/archive/2012/04/01/2429200.html
动态规划思想完全参照该篇博文
这篇文章的做法非常巧妙，AC后时间和空间都是目前提交中最优的。
mincost数组存储A站到B及A,B站之间的站的最小费用，从离A近的站开始求。
每次求最小费用有两个步骤
1.找到本站之前距离不超过L3的站的个数count
2.循环count次，将费用分成两段，A站到中间站+中间站到所求站。找到最小的费用。
A站到中间站存储在mincost中，中间站到所求站距离不超过L3，费用已知
开始有个疑问是，A站到X站中有X1和X2站，将费用分成三段，A站到X1站+X1站到X2站+X2站到X站，
三段费用才是最小费用，会不会出现这种情况？肯定不会，因为在求A到X站的最小费用时，
肯定已经求出A站到X2站的最小费用了，不可能存在一个X1站使整体的费用更小。
另外，不要忘记将费用分段，只有超出L3才用动态规划。
另外Java中初始化数组会默认元素为0，则不必再为mincost[0]赋值为0