Codeforces 19B Checkout Assistant：01 背包 DP 求最小代價覆蓋時間

題目大意

有 n 個商品，第 i 個需要時間 tᵢ 處理，代價 cᵢ。收銀員可同時處理多個商品，但總處理時間至少覆蓋所有選中商品的時間和。求最小總代價使得 Σ(tᵢ+1) ≥ n（因為處理一個商品佔用 1 單位時間槽，實際可並行）。

DP 建模

將 tᵢ 視為「覆蓋能力」，每選一個商品增加 tᵢ+1 的覆蓋。目標覆蓋 ≥ n。這是經典 01 背包：

• dp[j]：覆蓋能力恰為 j 的最小代價。
• 初始 dp[0]=0，其餘 INF。
• 轉移：dp[j + t[i]+1] = min(dp[j + t[i]+1], dp[j] + c[i])。
• 答案：min{ dp[j] | j ≥ n }。

代碼實現

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

const long long INF = 4e18; // 1e18 足夠
const int N = 2005;

long long dp[N<<1], c[N], t[N];

int main() {
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> t[i] >> c[i];
            t[i]++; // 實際覆蓋能力
        }
        fill(dp, dp + n + 1, INF);
        dp[0] = 0;

        long long ans = INF;
        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= 0; j--) {
                if (dp[j] == INF) continue;
                int nj = j + t[i];
                if (nj >= n) ans = min(ans, dp[j] + c[i]);
                else dp[nj] = min(dp[nj], dp[j] + c[i]);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵優化

• 狀態壓縮：只需維護 0~n 的覆蓋能力，超過 n 直接更新答案，不進入 DP 表。
• 逆序循環：01 背包必須從大到小更新 j，避免重複使用同一物品。
• INF 設定：用 4e18 避免加法溢出（cᵢ ≤ 10⁹, n ≤ 2000）。

複雜度分析

• 時間：O(n²) = 4e6，極快。
• 空間：O(n)。

總結

本題是「覆蓋型 01 背包」變體，關鍵在於將「並行處理」轉化為「時間槽覆蓋」模型。逆序 DP + 狀態截斷是標準技巧，代碼極其簡潔高效。