题解 | #最小花费#

#include <math.h>
#include <stdio.h>

//dp[i] = min{dp[i-1]+(i到i-1之间的合适的价位)...dp[i-n]+(i到i-n之间合适的价位)}
//dis[i] - dis[i-n]<l3
//把握好一旦距离超过l3，中间必须选一个站台买票就行，然后就看选哪个站台买票花销最小
//距离是给定的，只需求花费
//cost初始化状态：cost[start] = 0
//cost[start+1] = 第一到第二站台距离的花销


int l1,l2,l3,c1,c2,c3;
int get_price(int num){
    if (num<=l1){
        return c1;
    }else if (num<=l2) {
        return c2;
    }else {
        return c3;
    }
}

int main() {
    while (scanf("%d %d %d %d %d %d", &l1, &l2, &l3, &c1, &c2, &c3) != EOF) {
        int start,end,n;
        scanf("%d %d %d", &start, &end, &n);
        int dis[n+1], cost[end+1];
        dis[1] = 0;
        for (int i=2;i<=n;i++){
            scanf("%d", &dis[i]);
        }
        cost[start] = 0;
        cost[start+1] = get_price(dis[start+1]);
        for (int i=start+2;i<=end;i++){
            int min=cost[i-1]+get_price(dis[i] - dis[i-1]);
            for(int j=i-1;j>=start;j--){
                int d=dis[i]-dis[j];
                if(d>l3){
                    break;
                }else {
                    if(min > cost[j] + get_price(d))
                    min = cost[j] + get_price(d);
                }
            }
            cost[i] = min;
        }
        printf("%d\n",cost[end]);
    }
    return 0;
}