HDU 4502 吉哥系列故事——臨時工計劃：區間排程動態規劃解法詳解

題目大意

吉哥有 m 天假期（天數編號 1~m），共有 n 份工作，每份工作有起始日 s、結束日 e 與報酬 c。工作必須從 s 做到 e 才能領取報酬，且工作時間不可重疊（例如 [1,2] 與 [2,4] 衝突，因第 2 天只能做一份）。目標是在 m 天內安排工作獲取最大總報酬（第 m+1 天必須返校，超過 m 的工作不可選）。

資料範圍

• 測資組數 T ≤ 1000
• 假期天數 9 < m ≤ 100
• 工作數 0 ≤ n ≤ 1000
• s ≤ 100, e ≤ 100, s < e
• 報酬 c ≤ 10000

核心思路：按結束時間排序 + DP

這是經典的加權區間排程問題。將所有工作按結束時間 e 遞增排序（e 相同時按報酬 c 遞減），定義 dp[t] 為前 t 天可獲得的最大報酬。對每份工作 (s, e, c)，從 m 遞減至 e 更新：

dp[j] = max(dp[j], dp[s-1] + c)   // j 從 m 遞減至 e

最終答案為 dp[m]。

完整程式碼（C++，GNU++11 通過）

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int s, e, c;
    bool operator<(const Job& other) const {
        if (e != other.e) return e < other.e;
        return c > other.c;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; 
    if(!(cin >> T)) return 0;
    while (T--) {
        int m, n;
        cin >> m >> n;
        vector<Job> jobs(n);
        for (int i = 0; i < n; ++i) {
            cin >> jobs[i].s >> jobs[i].e >> jobs[i].c;
        }
        sort(jobs.begin(), jobs.end());
        
        vector<int> dp(m + 1, 0);
        for (const auto& job : jobs) {
            if (job.e > m) continue;           // 超過假期不可選
            for (int day = m; day >= job.e; --day) {
                dp[day] = max(dp[day], dp[job.s - 1] + job.c);
            }
        }
        cout << dp[m] << '\n';
    }
    return 0;
}

複雜度分析

• 排序：O(n log n)
• DP 狀態轉移：O(n * m)，m ≤ 100，n ≤ 1000，極快
• 空間：O(m)

關鍵細節提醒

1. 排序規則：先按 e 升序，再按 c 降序，確保同結束日時優先考慮高報酬工作。
2. 倒序更新：day 從 m 遞減至 e，避免同一工作被重複選取（0/1 背包特性）。
3. 邊界條件：dp[s-1] 當 s=1 時存取 dp[0]，初始化為 0 即可。
4. 過濾無效工作：e > m 的工作直接跳過，不參與 DP。

測試範例

Input:
1
10 5
1 5 100
3 10 10
5 10 100
1 4 2
6 12 266

Output:
102

解析：選 [1,4] 報酬 2 + [5,10] 報酬 100 = 102（注意 [6,12] 超過 m=10 不可選）。

延伸思考

若 m 較大（如 10^5），可改用座標壓縮 + 線段樹/樹狀陣列優化 DP，將轉移降為 O(log m)。本題 m ≤ 100，朴素 DP 完全足夠。