「Tyvj 3317」火车票 - 划分 DP

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

\cases{0< X≤L1 & C1 \\ L1< X≤L2 & C2 \\ L2< X≤L3 & C3}

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

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

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

链接

Tyvj 3317
CodeVS 1349

题解

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

f[i] = \min\{f[k]+cost(k,i),k{\in}[s,i) \ {\rm and} \ a[i]-a[k]≤L3\}

边界条件为

f[s] = 0

代码

#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;
}