最小花费

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] a;
    static int L1;
    static int L2;
    static int L3;
    static int C1;
    static int C2;
    static int C3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            String[] s1 = s.split(" ");
            L1 = Integer.parseInt(s1[0]);
            L2 = Integer.parseInt(s1[1]);
            L3 = Integer.parseInt(s1[2]);
            C1 = Integer.parseInt(s1[3]);
            C2 = Integer.parseInt(s1[4]);
            C3 = Integer.parseInt(s1[5]);
            String[] s2 = br.readLine().split(" ");
            int A = Integer.parseInt(s2[0]);
            int B = Integer.parseInt(s2[1]);
            int N = Integer.parseInt(br.readLine());
            a = new int[N + 1];
            for (int i = 2; i <= N; i++) {
                a[i] = Integer.parseInt(br.readLine());
                //a[i]表示第1站到第i站的距离 1～2为a[2]  1~3为a[3] ......
            }
            //数据录入完毕

            int[] dp = new int[N + 1 + A];
            //dp[i]表示A到第i站的最短花费
            dp[A] = 0;//A~A
            for (int i = A + 1; i <= B; i++) {
                dp[i] = Integer.MAX_VALUE;
                for (int j = A; j <= i; j++) {
                    int d = a[i] - a[j];
                    if (d <= L3)
                        dp[i] = Math.min(dp[i], dp[j] + cost(d));
                    else {
//                        continue;
                        int cost = 0;
                        for (int k = j; k < i; k++) {
                            cost += cost(a[k + 1] - a[k]);
                        }
                        dp[i] = Math.min(dp[i], dp[j] + cost);
                    }
                    //两站间距离大于L3时就跳过，不用计算
                    //因为要下车再买票，一直到剩下的几站距离小于等于L3为止（一定会有两站间距离小于等于L3的，因为每两个站之间的距离不超过L3）
                    //假设要算2～9站的最少票价，乘客原本坐到了5站，发现剩余距离远大于L3，那乘客就得往后坐一站，再次做比较，发现还大于L3，继续坐一站。。。。
                    //直到剩余的距离小于L3，这里假设7～9的距离<L3,这种情况下我买的票情况：2～5是最少花费（dp数组)+5～6的票价+6～7的票价+7～9的票价
                    //这种情况下一定不是最少票价，后期一定会被2~7的最少花费（dp数组)+7～9的票价所更新
                }
            }
            System.out.println(dp[B]);
        }

    }

    private static int cost(int distence) {
        int price = 0;
        if (distence <= L1) price = C1;
        else if (distence <= L2) price = C2;
        else price = C3;
        return price;
    }

}

package tsinghua;

import java.util.Scanner;

/*
 *	QQ:	825580813(一起来敲代码)
 */
public class MinCost {
	
	static int[] L = new int[3];
	static int[] C = new int[3];
	static int A, B, N;
	static int[] distance;		//distance[i] 表示 第1站 到 第i + 1站 的距离
	static int[] dp;			//dp[i] 表示 第一站 到 第i + 1站 的最小花费

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			for (int i = 0; i < L.length; ++i) {
				L[i] = sc.nextInt();
			}
			for (int i = 0; i < C.length; ++i) {
				C[i] = sc.nextInt();
			}
			A = sc.nextInt();
			B = sc.nextInt();
			N = sc.nextInt();
			distance = new int[N];
			for (int i = 1; i < distance.length; ++i) {
				distance[i] = sc.nextInt();
			}
			int res = getMinCost();
			System.out.println(res);
		}
		sc.close();
	}

	//用动态规划的方法求出dp的值
	private static int getMinCost() {
		dp = new int[distance.length];
		dp[1] = getPrice(distance[1]);	//第2站的最小花费就是 第1站 到 第2站 的花费.
		for (int i = 2; i < distance.length; ++i) {
			int interval = distance[i] - distance[i - 1];	//第i站 与 前一站 的间隔
			//第i站 的初始赋值,就是前一站的花费 + 前一站 到第 i 站的花费
			dp[i] = dp[i - 1] + getPrice(interval);			
			for (int j = i - 2; j >= 0; --j) {		//试探是否可以通过前几站 直接坐到 第i站(中途不下车)
				interval = distance[i] - distance[j];//第j站 到 第i站的间隔
				if (interval > L[2]) {		//如果间隔大于L3的话,j前面的站就不能直达第i站了,跳出
					break;
				}
				dp[i] = Math.min(dp[i], dp[j] + getPrice(interval));
			}
		}
		return dp[B - 1] - dp[A - 1];
	}

	//根据一段距离计算出花费
	private static int getPrice(int dis) {
		for (int i = 0; i < L.length; ++i) {
			if (dis <= L[i]) {
				return C[i];
			}
		}
		return 0;
	}

}