bzoj2287 POJ Challenge 消失之物（背包）

2287: 【POJ Challenge】消失之物

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 735  Solved: 413
[Submit][Status][Discuss]

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)的末位数字。

 

 

第一反应是跑前缀背包和后缀背包，但是发现是$n^3$的orz；

实际计算count数组时可以用FFT优化，复杂度$O(n^2·logn)$;

 

正解：（来自http://hzwer.com/2446.html）

递推求count时，分三种情况讨论：

　　1、$count[i][0]=1$；

　　2、$j<w[i]$时，不会用到第$i$个物品，因此$count[i][j]=dp[n][j]$；

　　3、$j>=w[i]$时，注意到使用第$i$个物品填满背包等价于不用第$i$个物品填充$m-w[i]$的体积；

　　　  因此$count[i][j]=dp[n][j]-count[i][j-w[i]]$；

复杂度$O(n^2)$；

AC GET☆DAZE

 

↓代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define ll long long
using namespace std;
int dp[2039][2039],wei[2039],con[2039][2039];
int main()
{
    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    for(a=1;a<=n;a++)
    {
        scanf("%d",&wei[a]);
    }
    dp[0][0]=1;
    for(a=1;a<=n;a++)
    {
        for(b=0;b<=m;b++)
        {
            if(b>=wei[a])
            {
                dp[a][b]+=dp[a-1][b-wei[a]];
            }
            dp[a][b]+=dp[a-1][b];
            dp[a][b]%=10;
        }
    }
    for(a=1;a<=n;a++)
    {
        con[a][0]=1;
        for(b=1;b<wei[a];b++)
        {
            con[a][b]=dp[n][b];
        }
        while(b<=m)
        {
            con[a][b]=(dp[n][b]-con[a][b-wei[a]]+10)%10;
            b++;
        }
    }
    for(a=1;a<=n;a++)
    {
        for(b=1;b<=m;b++)
        {
            printf("%d",con[a][b]);
        }
        cout<<endl;
    }
    return 0;
}