题解 | 最小花费

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define price(x) ((x) <= l2 ? ((x) <= l1 ? c1 : c2) : c3)
#define min(x, y) ((x) <= (y) ? (x) : (y))

int main() {
    int l1, l2, l3, c1, c2, c3, a, b, n;
    while (scanf("%d %d %d %d %d %d", &l1, &l2, &l3, &c1, &c2, &c3) != EOF) {
        scanf("%d %d", &a, &b);
        scanf("%d", &n);
        
        // 确保 a <= b
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }

        int* arr = (int*)malloc(sizeof(int) * (n + 1));
        arr[1] = 0;  // 起点距离为 0
        for (int i = 2; i <= n; i++) {
            scanf("%d", &arr[i]);
        }

        int size = b - a + 1;
        int* distance = (int*)malloc(sizeof(int) * size);
        int* dp = (int*)malloc(sizeof(int) * size);

        // 初始化 distance 和 dp
        for (int i = 0; i < size; i++) {
            distance[i] = arr[i + a] - arr[a];
            dp[i] = INT_MAX;  // 初始化为无穷大
        }
        dp[0] = 0;  // 起点花费为 0

        // 动态规划计算最小花费
        for (int i = 1; i < size; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int dist = distance[i] - distance[j];
                if (dist > l3) break;  // 超过 l3，直接跳过
                dp[i] = min(dp[i], dp[j] + price(dist));
            }
        }

        printf("%d\n", dp[size - 1]);

        // 释放内存
        free(arr);
        free(distance);
        free(dp);
    }
    return 0;
}