2013
12-12

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

0<S<=L1         C1
L1<S<=L2        C2
L2<S<=L3        C3

L1  L2  L3  C1  C2  C3
A  B
N
a[2]
a[3]
……
a[N]

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