HDU 4502 吉哥臨時工計劃 解題報告：區間 DP 優化

問題重述

m 天假期，n 份工作。每份工作有起始日 s、結束日 e、工資 c。工作不可重疊（時間交集為空）。選擇工作子集最大化總工資。m ≤ 100, n ≤ 1000。

DP 狀態定義

dp[i] = 前 i 天（第 1..i 天）能獲得的最大工資。答案為 dp[m]。

轉移方程

按結束時間 e 排序工作。對於工作 (s, e, c)：

dp[e] = max(dp[e], dp[s-1] + c)

並向後傳播：for (j=e+1; j<=m; ++j) dp[j] = max(dp[j], dp[e])，因為第 e 天結束的最優方案對後續天數也可用。

完整算法流程

1. 讀入工作，過濾 s<1 或 e>m 的無效工作。
2. 按 e 升序、s 降序、c 降序排序。
3. 初始化 dp[0..m] = 0。
4. 遍歷工作，更新 dp[e] 並向後傳播最大值。
5. 輸出 dp[m]。

代碼實現

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int m, n; scanf("%d%d", &m, &n);
        vector jobs;
        for (int i=0;i=1 && e<=m) jobs.push_back({s,e,c});
        }
        sort(jobs.begin(), jobs.end(), cmp);
        vector dp(m+1, 0);
        for (const auto& j : jobs) {
            int val = dp[j.s-1] + j.c;
            if (val > dp[j.e]) {
                for (int k=j.e; k<=m; ++k) dp[k] = val;
            }
        }
        printf("%d\n", dp[m]);
    }
}

為什麼向後傳播有效？

dp[i] 定義為前 i 天的最大工資，具有單調不減性。若在第 e 天獲得更優方案，則對所有 k ≥ e，dp[k] 至少可達到該值（選擇不工作即可）。

複雜度

• 排序：O(n log n)
• DP：最壞 O(n*m)，但 m≤100, n≤1000 僅 10^5 操作，極快。