ZOJ 3703 Happy Programming Contest：多目標優先級的 0/1 背包動態規劃

題目背景與三層優先級

比賽時長 T ≤ 1000，n ≤ 50 道題。每題有解題時間 tᵢ 與吸引力值 vᵢ。目標按優先級遞減：

1. 最大化總吸引力值；
2. 在吸引力相同前提下，最大化解題數；
3. 在前兩者相同前提下，最小化總罰時（罰時 = 各題提交時間之和）。

狀態定義與多維度 DP

經典 0/1 背包以時間為容量：dp[time] = {max_value, max_count, min_penalty}。
為避免結構體排序開銷，可用三個平行陣列：

• val[t]：時間 t 內可達到的最大吸引力；
• cnt[t]：對應 val[t] 時的最大題數；
• pen[t]：對應前兩者時的最小罰時。

狀態轉移：逆序迭代 + 條件更新

對每題 i，時間從 T 遞減至 tᵢ：

for (int t = T; t >= time[i]; --t) {
    int nt = t - time[i];
    long long nv = val[nt] + value[i];
    int nc = cnt[nt] + 1;
    long long np = pen[nt] + cnt[nt] + time[i]; // 罰時 = 前序罰時 + 當前提交時間

    if (nv > val[t] ||
        (nv == val[t] && nc > cnt[t]) ||
        (nv == val[t] && nc == cnt[t] && np < pen[t])) {
        val[t] = nv;
        cnt[t] = nc;
        pen[t] = np;
    }
}

罰時推導：若前序已解題數為 cnt[nt]，其提交時間總和為 pen[nt]，新題提交時間為 t，故新罰時 pen[nt] + t。原碼寫法 pen[nt] + cnt[nt] + time[i] 等價（因 t = nt + time[i]）。

答案提取

遍歷 t = 0..T，按相同優先級比較三元組 (val[t], cnt[t], pen[t]) 取最優。

複雜度與優化

• 時間 O(nT) = 5×10⁴，空間 O(T)，極輕量。
• 原碼變數命名 fuck 存罰時，建議改為 penalty 以利維護。
• 初始化：val[0]=0, cnt[0]=0, pen[0]=0；其餘 val = -INF 表示不可達。

總結

本題是「多目標優先級背包」的教科書級範例：將優先級編碼進狀態比較函數，單次掃描即可同時滿足三層優化條件。關鍵在於正確推導罰時遞推公式，並嚴格遵守 0/1 背包的逆序迭代原則。