题解 | 最小花费

#include <iostream>
#include<vector>
using namespace std;


int caculatecost(int distance, int L1, int L2, int L3, int C1, int C2, int C3) {
    if (distance <= L1)return C1;
    if (distance <= L2)return C2;
    if (distance <= L3)return C3;
    return 1000000000;
}



int main() {
    int L1, L2, L3, C1, C2, C3, A, B, N;

    while (cin >> L1 >> L2 >> L3 >> C1 >> C2 >> C3 >> A >> B >>
            N) { // 注意 while 处理多个 case
        int tmp;
        vector<int>v1;
        for (int i = 0; i < N - 1; i++) {
            cin >> tmp;
            v1.push_back(tmp);
        }
        vector<int>dp(N+1, 1000000000);
        dp[A]=0;
        for(int i=A;i<B;i++){
            for(int j=i+1;j<=B;j++){
                //注意这里的v1存储的是从第一个站到其他各站点的距离，所以要用j-2和i-2
                int distance=v1[j-2]-v1[ i-2];
                int cost=caculatecost(distance, L1, L2, L3, C1, C2, C3);
                dp[j]=min(dp[j],dp[i]+cost);
            }
        }
        cout<<dp[B]<<endl;
    }
}
// 64 位输出请用 printf("%lld")