2026.1.17 作业 - P4141 消失之物

题目描述

ftiasch 有 \(n\) 个物品, 体积分别是 \(w_1,w_2,\dots,w_n\)。由于她的疏忽，第 \(i\) 个物品丢失了。

“要使用剩下的 \(n-1\) 物品装满容积为 \(x\) 的背包，有几种方法呢？”——这是经典的问题了。

她把答案记为 \(\text{cnt}(i,x)\) ，想要得到所有\(i \in [1,n]\), \(x \in [1,m]\) 的 \(\text{cnt}(i,x)\) 表格。

输入格式

第一行两个整数 \(n,m\)，表示物品的数量和最大的容积。
第二行 \(n\) 个整数 \(w_1,w_2,\dots,w_n\)，表示每个物品的体积。

输出格式

输出一个 \(n \times m\) 的矩阵，表示 \(\text{cnt}(i,x)\) 的末位数字。

输入输出样例 #1

输入 #1

3 2
1 1 2

输出 #1

11
11
21

说明/提示

【数据范围】
对于 \(100\%\) 的数据，\(1\le n,m \le 2000\)，且 \(1\le w_i\le 2000\)。

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

#include <iostream>
using namespace std;
int n,m,w[2002],cnt[2002][2002],F[2002];
int main() {cin>>n>>m;for (int i=1;i<=n;i++) cin>>w[i];F[0]=1;for (int i=1;i<=n;i++)for (int j=m;j>=w[i];j--) F[j]=(F[j]+F[j-w[i]])%10;for (int i=1;i<=n;i++) {for (int j=0;j<w[i];j++) cnt[i][j]=F[j];for (int j=w[i];j<=m;j++) cnt[i][j]=(F[j]-cnt[i][j-w[i]]+10)%10;}for (int i=1;i<=n;i++) {for (int j=1;j<=m;j++) cout<<cnt[i][j]%10;cout<<endl;}return 0;
}