题解 | #最小花费#

/*
这题，评论区的答案都没我写得好
*/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int L1, L2, L3, C1, C2, C3;
int a, b;
int n;
vector<int> dis(n);

int price(int a, int b) {
    int distance = dis[b] - dis[a];
    if (L2 < distance && distance <= L3) return C3;
    if (L1 < distance && distance <= L2) return C2;
    if (0 < distance && distance <= L1) return C1;
    return -1;
}

int main() {
    cin >> L1 >> L2 >> L3 >> C1 >> C2 >> C3;
    cin >> a >> b;
    cin >> n;
    dis.resize(n + 1);
    dis[1] = 0;
    for (int i = 2; i <= n; i++) {
        cin >> dis[i];//第i个站与i+1个站的距离
    }
    vector<int> dp(b + 1);
    dp[a] = 0;
    for (int i = a + 1; i <= b; i++) {
        dp[i] = INT_MAX;
        int k = i - 1;
        while (price(k, i) != -1 && k >= a) {
            dp[i] = dp[k] + price(k, i) < dp[i] ? dp[k] + price(k, i) : dp[i];
            k--;
        }
    }
    cout << dp[b] << endl;
}

// 64 位输出请用 printf("%lld")
/*

dp[j]表示从起始站点上车，到j点下车的最低票价
dp[j]= min(dp[k]+price(k),...), 其中k为所有与j点距离小于L3的站点,price[k]表示从k到j点的花费


100 500 1000 100 450 800
3 86
100
468
865
1644
2556
3328
3607
4447
5430
5695
6626
7142
7973
8802
9523
9724
10046
10054
10955
11387
12032
12182
13078
13465
13850
13944
14630
15306
16104
17072
17662
17857
18412
18635
19217
19641
19655
19962
20961
21343
21687
21824
22502
23486
24241
24829
25824
26393
27251
27569
28451
29274
30025
30986
31526
32252
33224
33573
34404
34685
35563
36088
36176
36193
37077
37336
37847
37947
38595
38918
39476
39983
40332
40388
41014
41217
41577
42546
42646
42912
42949
43137
43180
43583
43805
44400
44892
45357
45471
46208
46938
47774
48157
49129
49638
49980
50741
50991
51961
52174


*/