POJ 1661 Help Jimmy：二維 DP 求最早落地時間

題目大意

• N 個水平平台，每個有左/右端點 l, r 和高度 h。
• Jimmy 從 (x, y) 落下，下落/水平速度 1m/s，最大落差 max。
• 求到達地面（高度 0）的最早時間。

DP 狀態定義

按高度升序排序平台（含起點、地面）。
dp[i][0]：從平台 i 左端點落地最短時間。
dp[i][1]：從平台 i 右端點落地最短時間。

狀態轉移

對平台 i，向下尋找第一個能落上的平台 k（高度差 ≤ max 且水平投影重疊）。

dp[i][0] = h[i] - h[k] + min(
    dp[k][0] + l[i] - l[k],   // 從 k 左端走到 i 左端
    dp[k][1] + r[k] - l[i]    // 從 k 右端走到 i 左端
)
dp[i][1] = h[i] - h[k] + min(
    dp[k][1] + r[k] - r[i],
    dp[k][0] + r[i] - l[k]
)

若無平台可落，直接落地：dp[i][*] = h[i]（若落差 ≤ max），否則 INF。

完整代碼

#include 
using namespace std;
const int INF = 1e9;
struct Plat { int l, r, h; };
bool cmpH(const Plat& a, const Plat& b) { return a.h < b.h; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, x, y, maxFall; cin >> n >> x >> y >> maxFall;
        vector p(n+2);
        for (int i = 1; i <= n; ++i) cin >> p[i].l >> p[i].r >> p[i].h;
        p[0] = {x, x, y};           // 起點
        p[n+1] = {-20000, 20000, 0}; // 地面
        sort(p.begin(), p.end(), cmpH);
        int N = n + 2;
        vector> dp(N, {INF, INF});
        for (int i = 1; i < N; ++i) {
            // 找正下方第一個可落平台
            int k = i - 1;
            while (k >= 0 && p[i].h - p[k].h <= maxFall) {
                // 左端點能否落在 k 上
                if (p[i].l >= p[k].l && p[i].l <= p[k].r) {
                    if (k == 0) dp[i][0] = p[i].h;
                    else dp[i][0] = p[i].h - p[k].h + min(
                        dp[k][0] + p[i].l - p[k].l,
                        dp[k][1] + p[k].r - p[i].l
                    );
                    break;
                }
                --k;
            }
            if (p[i].h - (k>=0?p[k].h:0) > maxFall) dp[i][0] = INF;
            // 右端點同理
            k = i - 1;
            while (k >= 0 && p[i].h - p[k].h <= maxFall) {
                if (p[i].r >= p[k].l && p[i].r <= p[k].r) {
                    if (k == 0) dp[i][1] = p[i].h;
                    else dp[i][1] = p[i].h - p[k].h + min(
                        dp[k][1] + p[k].r - p[i].r,
                        dp[k][0] + p[i].r - p[k].l
                    );
                    break;
                }
                --k;
            }
            if (p[i].h - (k>=0?p[k].h:0) > maxFall) dp[i][1] = INF;
        }
        cout << min(dp[N-1][0], dp[N-1][1]) << "\n";
    }
    return 0;
}

複雜度

• 排序 O(N log N)。
• DP 兩層循環 O(N²)，N ≤ 1000 可接受。