BZOJ2287: 【POJ Challenge】消失之物(背包dp)

題意

ftiasch 有 N 個物品, 體積分別是 W₁, W₂, ..., W_N。 由於她的疏忽, 第 i 個物品丟失了。 “要使用剩下的 N - 1 物品裝滿容積為 x 的背包，有幾種方法呢？” -- 這是經典的問題了。她把答案記為 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。

Sol

Orz hzwer

這題可能有三種做法吧。。

第一種是分治背包

第二種是NTT優化暴力

第三種是$O(nm)$的神仙dp

這裡只說一下第三種

首先設$f[i][j]$表示前$i$個物品選了$j$個，然後就是裸的完全背包

設$cnt[i][x]$表示答案

考慮這玩意兒怎麼轉移

1. $cnt[i][0] = 1$
2. 若$j \le w[i]$，$cnt[i][j] = f[n][j]$
3. 若$j \geqslant w[i]$，$cnt[i][j] = f[n][j] - cnt[i][j - w[i]]$

第三個的轉移非常神仙，反正我是沒想出來，我們考慮用總的方案數減去用了改物品的方案數，我們發現直接算不是很好算，然後補集轉化一下，用了物品$i$，體積為$j$，那麼其他物品的體積為$j - w[i]$，這裡的其他物品，也就是不用$i$的情況，也就是原來的$cnt$數組！！好神仙啊qwq

#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
//#define int long long 
#define Pair pair<int, int> 
#define fi first
#define se second
#define MP(x, y) make_pair(x, y)
using namespace std;
const int MAXN = 1e6 + 10, mod = 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 
    return x * f;
}
int N, M;
int w[MAXN], f[2001][2001], cnt[2001][2001];
main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) w[i] = read();
    f[0][0] = 1;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= M; j++) {
            (f[i][j] += f[i - 1][j]) %= mod;//不裝 
            if(j >= w[i]) (f[i][j] += f[i - 1][j - w[i]]) %= mod;
        }
    }
    for(int i = 1; i <= N; i++) {
        cnt[i][0] = 1;
        for(int j = 1; j <= M; j++) {
            if(j < w[i]) cnt[i][j] = f[N][j] % mod;
            else cnt[i][j] = (f[N][j] - cnt[i][j - w[i]] + mod) % mod;
        }
    }
    for(int i = 1; i <= N; i++, puts(""))
        for(int j = 1; j <= M; j++)
            printf("%d", cnt[i][j] % mod);
    return 0;
}
/*
3 2
1 1 2
*/