POJ 3257 過山車建設：動態規劃解法詳解

問題描述

需建設一條從位置 1 到 L 的過山車軌道，給出 n 段可選建設方案。每段包含起點、終點、成本與趣味值。要求相鄰軌道首尾相連覆蓋 1-L，總成本不超過 B，求最大總趣味值。

動態規劃模型設計

定義二維 DP 陣列：dp[i][j] 表示恰好建設到位置 i 且花費成本 j 時的最大趣味值。

狀態轉移

1. 將所有建設方案按起點排序
2. 初始化：dp[0][0] = 0，其餘為 -1（不可達）
3. 對每個方案 k（起點 s，終點 e，趣味 f，成本 c）：

   for j = 0 to B:
       if dp[s-1][j] != -1 and j + c <= B:
           dp[e][j+c] = max(dp[e][j+c], dp[s-1][j] + f)

4. 答案：max(dp[L][j]) for j = 0..B

關鍵實作細節

• 輸入處理：方案的終點需加上起點（e += s），起點 +1（s++）以符合 1-based 邏輯
• 陣列大小：dp[1100][1010] 滿足 L ≤ 1000, B ≤ 1000 限制
• 使用 long long 防止趣味值溢位
• 排序確保 DP 依賴的前驅狀態已計算完成

複雜度分析

• 時間：O(n × B) ≈ 10⁷ 次操作，符合限制
• 空間：O(L × B) ≈ 4.4 MB

完整代碼

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct Segment {
    int s, e, fun, cost;
    bool operator<(const Segment& other) const {
        return s != other.s ? s < other.s : e < other.e;
    }
} seg[10010];

long long dp[1100][1010];

int main() {
    int L, n, B;
    while (scanf("%d%d%d", &L, &n, &B) == 3) {
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%d%d", &seg[i].s, &seg[i].e, &seg[i].fun, &seg[i].cost);
            seg[i].e += seg[i].s;
            seg[i].s++;
        }
        sort(seg, seg + n);
        dp[0][0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= B; ++j) {
                if (dp[seg[i].s - 1][j] != -1) {
                    if (j + seg[i].cost > B) continue;
                    long long &cur = dp[seg[i].e][j + seg[i].cost];
                    cur = max(cur, dp[seg[i].s - 1][j] + seg[i].fun);
                }
            }
        }
        long long ans = -1;
        for (int j = 0; j <= B; ++j) ans = max(ans, dp[L][j]);
        printf("%lld\n", ans);
    }
    return 0;
}

核心洞見

本題展示了「區間覆蓋 + 成本約束」的經典 DP 模式：將軌道段視為有向邊，位置為節點，成本為第二維度，透過排序保證拓撲順序，實現高效狀態轉移。