HDU 4502 吉哥系列故事——臨時工計劃（區間調度 DP）

HDU 4502 臨時工計劃 - 加權區間調度 DP

M 天假期，N 份工作。每份工作有起始日 s、結束日 e、工資 c。工作不可重疊（時間不衝突）。求最大總工資。

問題建模

經典加權區間調度問題。按結束時間排序，DP[i] = 前 i 天最大工資。

狀態轉移

對每個工作 (s,e,c)，對天數 j 從 M 遞減到 e：

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

含義：在第 j 天結束時，選擇做這個工作（從 s 到 e），獲得工資 c，加上 s-1 天前的最優值。

完整代碼實現

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

struct Job { int s, e, c; } jobs[10005];

bool cmp(const Job& a, const Job& b) { return a.e < b.e; }

int dp[10005];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int m, n; scanf("%d%d", &m, &n);
        for (int i = 0; i < n; i++) scanf("%d%d%d", &jobs[i].s, &jobs[i].e, &jobs[i].c);
        sort(jobs, jobs+n, cmp);
        
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= jobs[i].e; j--) {
                dp[j] = max(dp[j], dp[jobs[i].s - 1] + jobs[i].c);
            }
        }
        printf("%d\n", dp[m]);
    }
    return 0;
}

關鍵點解析

• 按結束時間排序：保證 DP 轉移時 dp[s-1] 已計算完畢
• 逆序遍歷 j：01 背包風格，避免同一工作被重複使用
• dp[s-1]：工作從 s 開始，前 s-1 天的最優值
• 時間複雜度：O(N × M) = 1000 × 100 = 100,000，極快

樣例驗證

輸入：

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

工作按 e 排序：(1,4,2), (1,5,100), (3,10,10), (5,10,100), (6,12,266)

最優選擇：(1,4,2) + (5,10,100) = 102，匹配樣例輸出。

避坑指南

• M ≤ 100，dp 數組開 105 即可
• 工作結束日可能 > M（如樣例 12），但題目說 M+1 天必須返校，故 e > M 的工作實際不可做，代碼中 j 從 M 遞減自然處理
• 多測試用例，每次重置 dp