题解 | #最小花费#

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
vector<int> dis;
int main() {
    //处理一下输入，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3
    //dis[i]代表第i个车站距离第一个车站的距离，那么显然dis[0]随意赋值
    //dis[1]=1,剩下的话依据题意输入即可
    int l1, l2, l3, c1, c2, c3;
    while (cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3) {
        dis.clear();
        dis.push_back(-1);
        dis.push_back(0);
        //start和end是起始站和终点站
        int start, end;
        cin >> start >> end;
        int N;//火车站数量
        cin >> N;
        int dp[N + 1][N +
                      1]; //dp[i][j]表示第i个车站出发去第j个车站的最小花费
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] =
                    INT_MAX; //因为我们后面要取小值，所以初始化尽量最大
            }
        }
        for (int i = 1; i <= N; i++) {
            dp[i][i] =
                0; //注意一下从i车站出发去i车站的话，最小花费应该是0
        }
        int x;
        int num = N - 1;
        //输入N-1个整数，分别代表从该线路上的第一个站，到第2个站，第3个站，……，第N个站的距离。
        while (num--) {
            cin >> x;
            dis.push_back(x);
        }
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                int d = dis[j];
                int k = j - 1;
                int c = k;
                //依次比较上一趟应该买三种中的哪一种(前提是要能买)
                while (d - dis[k] <= l1 && k >= i) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + c1);
                    k--;
                }
                k = c;
                while (d - dis[k] <= l2 && k >= i) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + c2);
                    k--;
                }
                k = c;
                while (d - dis[k] <= l3 && k >= i) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + c3);
                    k--;
                }
            }
        }
        cout << dp[start][end] << endl;
    }
}
// 64 位输出请用 printf("%lld")