HDU 3535 AreYouBusy：混合背包 DP 狀態轉移詳解

題目大意

在總時間 T 內完成 n 堆工作，每堆有 num[i] 個子任務，耗時 cost[i][j]、幸福感 val[i][j]。每堆工作有屬性 flag[i]：

• 0：至少選 1 個（分組背包變形）；
• 1：最多選 1 個（標準分組背包）；
• 2：任意選（01 背包，可全不選）。

求最大幸福感，無可行解輸出 -1。

狀態定義

dp[i][j]：前 i 堆工作、耗時 j 獲得的最大幸福感（-1 表不可達）。容量 j 從 0 開始，注意迴圈下界。

三種屬性的轉移方程

flag = 2（01 背包，可不選）

for k = 1..num[i]
    for j = m .. cost[i][k]
        dp[i][j] = max(dp[i][j],
                       dp[i][j-cost] + val,      // 本組多選
                       dp[i-1][j-cost] + val);   // 從上組轉移
// 最後複製上組結果：dp[i][j] = max(dp[i][j], dp[i-1][j])

flag = 1（分組背包，最多 1 個）

for j = m .. 0
    for k = 1..num[i]
        if j >= cost[i][k]
            dp[i][j] = max(dp[i][j], dp[i-1][j-cost] + val);
// 複製上組結果

flag = 0（至少 1 個，分組背包變形）

for k = 1..num[i]
    for j = m .. cost[i][k]
        dp[i][j] = max(dp[i][j],
                       dp[i][j-cost] + val,      // 本組已選過再選
                       dp[i-1][j-cost] + val);   // 本組第一次選
// 不複製上組結果（強制至少選 1 個）

合法性檢查與答案提取

每組處理完檢查 dp[i][*] 是否全為 -1，若是直接返回 -1。最終答案為 max(dp[n][0..m])。

關鍵 Trick

• 容量從 0 起算，迴圈下界包含 0；
• 初始化 dp[0][0] = 0，其餘 -1；
• 三種轉移統一在二維陣列上完成，空間 O(n·m) 可滾動優化至 O(m)（但需小心 flag=0 的本組複用）。