Codeforces 480D Parcels - 動態規劃優化貨物堆疊收益

問題描述

有平板承重 S。N 件貨物 (N ≤ 500)，每件有到達時間 in、取走時間 out、重量 w、承重 s、利潤 v。貨物疊放：上層總重 ≤ 下層承重，總重 ≤ S。只能從頂部取走。若貨物在 [in, out] 內完整存放，獲得利潤 v。求最大利潤。

核心思路：時間排序 + 區間 DP + 前綴最大值優化

1. 排序策略

按 out 升序、in 降序排序。並添加虛擬貨物 0：in=0, out=2*MAXN, w=0, s=S, v=0 作為底板。這確保：若貨物 i 在 j 之下，則 out_i ≥ out_j 且 in_i ≤ in_j (外層時間區間包含內層)。

2. DP 定義

dp[i][w] = 考慮前 i 個貨物 (按排序後順序)，且第 i 個貨物被選作當前頂部貨物，其上方已放貨物總重為 w 時的最大利潤。w ∈ [w_i, S]。

3. 轉移優化

對於固定 i，枚舉 w。內層需考慮 j < i 且 in_i ≤ in_j 且 out_j ≤ out_i 的貨物 j 作為下一層。直接枚舉 j 並更新 w' = min(s_i, w - w_i) 會導致 O(N²S)。

關鍵優化：利用時間軸數組 f[t] 維護「時刻 t 前已處理完畢的貨物組合的最大利潤」。對於當前 i，初始化 f[in_i] = 0。按時間 t 從 in_i 推進到 out_i：

• f[t] = max(f[t], f[t-1]) (不放新貨物)。
• 對於所有 out_j == t 且滿足條件的 j，f[t] = max(f[t], f[in_j] + dp[j][w']) (放入貨物 j)。

4. 複雜度

外層 i: N。中層 w: S (≤ 1000)。內層時間推進: O(MAX_TIME) ≈ 1000。總 O(N·S·T) ≈ 500·1000·1000 = 5e8 偏大，但實際常數小且可優化 (如只遍歷有貨物的時間點)。Codeforces 官方題解給出 O(N·S) 做法，利用 f 數組大小 2N，每 i 掃描一次時間軸。

參考代碼 (官方簡化版)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
struct Parcel { int in, out, w, s, v; } p[MAXN];

bool cmp(Parcel a, Parcel b) {
    return a.out < b.out || (a.out == b.out && a.in > b.in);
}

int dp[MAXN][2005], f[2005];

int main() {
    int N, S; scanf("%d%d", &N, &S);
    p[0] = {0, 2*MAXN, 0, S, 0};
    for (int i = 1; i <= N; i++) scanf("%d%d%d%d%d", &p[i].in, &p[i].out, &p[i].w, &p[i].s, &p[i].v);
    sort(p, p+N+1, cmp);

    for (int i = 0; i <= N; i++) {
        for (int w = p[i].w; w <= S; w++) {
            int lim = min(p[i].s, w - p[i].w);
            fill(f, f + 2*MAXN + 2, 0);
            for (int j = 0; j < i; j++) if (p[j].in >= p[i].in) {
                for (int t = p[j].in; t <= p[j].out; t++) f[t] = max(f[t], f[t-1]);
                f[p[j].out] = max(f[p[j].out], f[p[j].in] + dp[j][lim]);
            }
            for (int t = p[i].in; t <= p[i].out; t++) f[t] = max(f[t], f[t-1]);
            dp[i][w] = f[p[i].out] + p[i].v;
        }
    }
    printf("%d\n", dp[N][S]);
    return 0;
}

關鍵點總結

• 時間區間包含關係 → 排序 + DP 狀態定義。
• 利用 f[t] 在時間軸上做前綴最大值，將二維轉移降為一維掃描。
• 虛擬底板統一邊界條件。
• 答案在 dp[N][S] (虛擬貨物排序後最後)。