「Tyvj 3317」火车票 - 划分 DP

发表于 | 分类于

铁路线上有n（2 ≤ n ≤ 10000）个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示：

其中L1，L2，L3，C1，C2，C3都是已知的正整数，且( , )。显然若两站之间的距离大于 L3，那么从一站到另一站至少要买两张票。

注意：每一张票在使用时只能从一站开始到另一站结束。

对于给出的起点和终点，求出最省钱的方案。

链接

Tyvj 3317
CodeVS 1349

题解

以经过火车站站点的数量划分阶段，用 表示从站点 0 到站点 i 的距离，用 表示从起点 s 到站点 i 所需要的最少花费，则转移方程为：

边界条件为

代码

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 10000;

int n, a[MAXN], s, t;
int L1, L2, L3, C1, C2, C3;

int ans[MAXN];
bool calced[MAXN];

inline int cost(int s, int t) {
    int L = a[t - 1] - a[s - 1];
    if (L > L3) return INT_MAX;
    else if (L > L2) return C3;
    else if (L > L1) return C2;
    else return C1;
}

int search(int i) {
    if (i == s) return 0;

    if (!calced[i - 1]) {
        ans[i - 1] = INT_MAX;
        for (int k = s; k < i; k++) {
            if (cost(k, i) == INT_MAX) continue;
            ans[i - 1] = std::min(ans[i - 1], search(k) + cost(k, i));
        }
        calced[i - 1] = true;
    }

    return ans[i - 1];
}

int main() {
    scanf("%d %d %d %d %d %d", &L1, &L2, &L3, &C1, &C2, &C3);
    scanf("%d\n%d %d", &n, &s, &t);
    for (int i = 1; i < n; i++) {
        scanf("%d", &a[i]);
    }

    if (s > t) std::swap(s, t);

    printf("%d\n", search(t));

    return 0;
}