BZOJ 2287 [POJ Challenge] 消失之物 —— 背包 DP + 排除單個物品技巧

BZOJ 2287：N, M ≤ 2000，N 個物品體積 W[i]，求對每個 i 和容量 x (1..M)，不選第 i 個物品裝滿背包的方案數個位數字。輸出 N×M 矩陣。

一、核心洞察

設 f[j] = 所有物品裝滿容量 j 的方案數（完全背包/01背包視題意，本題為 01 背包，每物品用一次）。
設 g[i][j] = 不選第 i 個物品裝滿 j 的方案數。
關鍵遞推：

if (j < W[i]) g[i][j] = f[j];           // 容量不足以裝物品 i，不選 i 等價於全選
else g[i][j] = f[j] - g[i][j - W[i]];    // 容量夠時，全選方案 = 不選 i 方案 + 選 i 方案
// 選 i 方案 = 不選 i 且裝滿 j-W[i] 的方案 = g[i][j-W[i]]

二、算法流程

1. 先跑一遍 01 背包得到 f[0..M]（滾動數組）。
2. 對每個物品 i，按容量 0..M 計算 g[j]（可一維滾動）。
3. 輸出 g[j] % 10。

三、完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n, m, w[MAXN], f[MAXN], g[MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);

    // 01 背包求 f
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= w[i]; --j)
            f[j] = (f[j] + f[j - w[i]]) % 10; // 只需個位，直接模 10 防溢出

    // 對每個物品計算 g 並輸出
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < w[i]; ++j) g[j] = f[j];
        for (int j = w[i]; j <= m; ++j) {
            g[j] = f[j] - g[j - w[i]];
            if (g[j] < 0) g[j] += 10; // 保證非負個位
        }
        for (int j = 1; j <= m; ++j) printf("%d", g[j] % 10);
        puts("");
    }
    return 0;
}

四、複雜度

• 時間：O(N·M) = 4×10⁶，極快。
• 空間：O(M) 兩個一維數組。

五、關鍵細節

1. 題目只需個位數字 → 全程 %10 運算，避免大整數。
2. g[j] = f[j] - g[j-W[i]] 可能出現負數，+10 修正。
3. 背包循環 j = m; j >= w[i]; --j 保證 01 背包每物品用一次。