bzoj 2287 【POJ Challenge】消失之物 背包動規

Description

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

Input

第1行：兩個整數 N (1 ≤ N ≤ 2 × 103) 和 M (1 ≤ M ≤ 2 × 103)，物品的數量和最大的容積。

第2行： N 個整數 W1, W2, …, WN, 物品的體積。

Output

一個 N × M 的矩陣， Count(i, x)的末位數字。

Sample Input

3 2

1 1 2

Sample Output

11

11

21

HINT

#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005],f[2005],g[2005];
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    f[0]=1;
    for (int i=1;i<=n;i++)
        for (int j=m;j>=a[i];j--)
            (f[j]+=f[j-a[i]])%=10;
    for (int i=1;i<=n;i++){
        for (int j=0;j<a[i];j++) g[j]=f[j];
        for (int j=a[i];j<=m;j++)
            g[j]=(f[j]-g[j-a[i]]+10)%10;
        for (int j=1;j<=m;j++) printf("%d",g[j]);
        putchar('\n');
    }
    return 0;
}