HDU 2059: 龜兔賽跑 - 動態規劃最短時間

問題描述

烏龜和兔子賽跑，路程 L 米，有 n 個充電站（含起點終點共 n+2 站）。兔子有電動車，充滿電可行 C 米，電動速度 vt1，人力速度 vt2 (vt1 > vt2)，充電耗時 t。烏龜匀速 vr。求兔子最少用時，若比烏龜快輸出 "Good job,rabbit!" 否則 "What a pity rabbit!"。注意：每次必須充滿電，不能使用剩餘電量。

動態規劃模型

站點 0~n+1，dp[i] 表示到達站點 i 的最短時間。轉移：對每個 j < i，計算從 j 到 i 的最短耗時 cost，dp[i] = min(dp[i], dp[j] + cost)。
cost 取兩種策略較小值：
1. 用電動車：若距離 len ≤ C，時間 = len/vt1；否則 = C/vt1 + (len-C)/vt2，另加充電時間 t（j>0 時）。
2. 全程人力：len/vt2。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const double INF = 1e9;

int main() {
    int L, n, C, T, vr, vt1, vt2;
    while (cin >> L) {
        cin >> n >> C >> T;
        cin >> vr >> vt1 >> vt2;
        vector<int> pos(n+2);
        for (int i = 1; i <= n; ++i) cin >> pos[i];
        pos[n+1] = L;
        vector<double> dp(n+2, INF);
        dp[0] = 0;
        for (int i = 1; i <= n+1; ++i) {
            for (int j = 0; j < i; ++j) {
                int len = pos[i] - pos[j];
                double t1, t2 = len * 1.0 / vt2;
                if (len <= C) t1 = len * 1.0 / vt1;
                else t1 = C * 1.0 / vt1 + (len - C) * 1.0 / vt2;
                if (j) t1 += T;
                t1 = min(t1, t2);
                dp[i] = min(dp[i], dp[j] + t1);
            }
        }
        double rabbit = dp[n+1], turtle = L * 1.0 / vr;
        if (rabbit < turtle) cout << "Good job,rabbit!" << endl;
        else cout << "What a pity rabbit!" << endl;
    }
    return 0;
}