描述 Description
ftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” – 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有 1 <= i <= N, 1 <= x <= M 的 Count(i, x) 表格。
输入格式 InputFormat
第 1 行：两个整数 N (1 ≤ N ≤ 2 × 103) 和 M (1 ≤ M ≤ 2 × 103)，物品的数量和最大的容积。
第 2 行：N 个整数 W1, W2, …, WN, 物品的体积。
输出格式 OutputFormat
一个 N×M 的矩阵，Count(i, x) 的末位数字。
样例输入 SampleInput
3 2
1 1 2
样例输出 SampleOutput
11
11
21
用 \(f[i][j]\) 表示前 \(i\) 个物品装容积为 \(j\) 的背包的方案数。则 \[ f[i][j]=f[i-1][j]+f[i-1][j-a[i]] \]
用 \(g[i][j]\) 表示前 \(i-1\) 个物品装容积为 \(j\) 的背包的方案数。则 \[ g[i][j]=f[n][j]-g[i][j-a[i]] \]
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=2005;
int i,j,t,n,m,l,r,k,z,y,x;
int a[maxn],f[maxn],g[maxn];
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
f[0]=1;
for (i=1;i<=n;i++) for (j=m;j>=a[i];j--) f[j]=(f[j]+f[j-a[i]])%10;
for (i=1;i<=n;i++)
{
for (j=0;j<=m;j++) g[j]=(j<a[i])?(f[j]):(((f[j]-g[j-a[i]])%10+10)%10);
for (j=1;j<=m;j++) printf("%d",g[j]);
printf("\n");
}
return 0;
}