BZOJ 2287 【POJ Challenge】消失之物

2287: 【POJ Challenge】消失之物

Description

ftiasch 有 N 个物品, 体积分别是 W₁, W₂, ..., W_N。由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” -- 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。

Input

第1行：两个整数 N (1 ≤ N ≤ 2 × 10³) 和 M (1 ≤ M ≤ 2 × 10³)，物品的数量和最大的容积。

第2行： N 个整数 W₁, W₂, ..., W_N, 物品的体积。

Output

一个 N × M 的矩阵， Count(i, x)的末位数字。

Sample Input

3 2
1 1 2

Sample Output

11
11
21

HINT

如果物品3丢失的话，只有一种方法装满容量是2的背包，即选择物品1和物品2。

　　如果说这是一道水题，不错。但如果说这仅仅是一道水题，那我会很生气。

　　背包问题当然很经典。f[i][j]表示前i个物品恰好装满容量为j的背包的方案数。显然可得：

　　初始状态：f[0][0]=1,f[0][j]=0(j≠0)

　　状态转移：f[i][j]+=f[i-1][j-w[i]](j>w[i])

　　然后我们继续。要算出c[i][j]表示除去第i个物品后剩下n-1个物品恰好装满容量为j的背包的方案数。亦可得：

　　c[i][0]=1

　　c[i][j]=f[n][j] (j<w[i]) 显然i号物品装不下

　　c[i][j]=f[n][j]-c[i][j-w[i]](j>=w[i]) f[n][j]是用了n种物品，我们要减去使用了i的方案数。而使用了i的方案数=c[i][j-w[i]]

　　当然，我们可以把空间降维，于是空间O(m)，时间O(nm)。

　　但是！！！

　　我们为什么一定要这样做？

　　法2：网上有一神犇算出了前缀与后缀的方案数（上述的f即为前缀方案数）。然后对于每一个不能取的i，他对i-1的前缀与i+1的后缀做了值域卷积FFT。空间O(nm)，时间O(nmlog m)。

　　法3：上面的做法其实十分暴力。但是，我们可以使用一些不一样的做法来实现法2的思想。

　　这个方法很值得推广，叫做“分治背包”。

　　先想更彻底的暴力。对于每一个物品，我们都需要算出除它以外物品叠加产生的答案。这样的时间复杂度是O(n*n*m)。

　　但是，我们可以发现：中间有很多统计是重复的。甚至说，是大多数也不为过。如果可以削去一些重复运算，那么效率会大大提高。

　　而现在，我们试图算出1~n这个整体中每一个数的ans，以此减少重复运算，我们可以使用二分。可以用类似于“线段树”的画风来理解这个问题，最开始我们在1~n这条线段上，它在DFS树上有2个儿子，一个是1~mid，另一个是mid+1~rg。这样递归下去，最后lf==rg，我们试图在此时输出i=lf的答案。

　　我们已经说过，对于一个数i，我们需要把1~i-1与i+1~n号物品的影响都叠加一遍。而这可以使用DFS回溯解决。现在需要算出lf~rg的答案。可知，mid+1~rg号物品的影响一定会被叠入lf~mid中的每一个物品中。

　　话不多说了，直接上代码（多读几遍就懂了）：

 1 /**************************************************************
 2     Problem: 2287
 3     User: Doggu
 4     Language: C++
 5     Result: Accepted
 6     Time:368 ms
 7     Memory:924 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 const int S = 12;
12 const int N = 2010;
13 const int M = 2010;
14 int n, m, w[N], dp[S][M];
15 void solve(int dep,int lf,int rg) {
16     if(lf==rg) {
17         for( int j = 1; j <= m; j++ ) printf("%d",dp[dep][j]);
18         printf("
");
19         return ;
20     }
21     int mid=(lf+rg)>>1;
22     for( int j = 0; j <= m; j++ ) dp[dep+1][j]=dp[dep][j];
23     for( int i = mid+1; i <= rg; i++ )
24         for( int j = m; j >= w[i]; j-- )
25             dp[dep+1][j]+=dp[dep+1][j-w[i]], dp[dep+1][j]%=10;
26     solve(dep+1,lf,mid);
27     for( int j = 0; j <= m; j++ ) dp[dep+1][j]=dp[dep][j];
28     for( int i = lf; i <= mid; i++ )
29         for( int j = m; j >= w[i]; j-- )
30             dp[dep+1][j]+=dp[dep+1][j-w[i]], dp[dep+1][j]%=10;
31     solve(dep+1,mid+1,rg);
32 }
33 int main() {
34     scanf("%d%d",&n,&m);
35     for( int i = 1; i <= n; i++ ) scanf("%d",&w[i]);
36     dp[0][0]=1;
37     solve(0,1,n);
38     return 0;
39 }
40

　　如果你看懂了，那我们就可以继续了。因为，背包问题是很容易插入新物品的，且插入的顺序对最后结果不会产生影响。而一般情况下，我们会统计前缀。在分治中，我们的顺序变了，但是效果是完全一样的。请注意，对于“整体DP以去重”这一方法，该条件极其必要的。

　　最后说一下，如果用分治背包，空间是O(mlog n)的，时间是O(nmlog n)的。

　　如果很懵，或是已经听懂了，可以再看一看：旧题新做：FLOJ Round #19 A 最短路

　　附录·速度比较：

分治背包	924 kb	368 ms	889 B
法1压缩空间	844 kb	356 ms	546 B
法1平方空间	16944 kb	364 ms	523 B