题解 : 消失之物

1.题意:

地址：https://www.luogu.com.cn/problem/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)%10$ 表格。

2.思路：

很显然，可以轻松地求出使用所有物品装满容积 j 的方案数

$f[i][j]$表示使用前 i 个物品的容积为 j 的背包方案数

令$g[i][j]$表示不使用第 i 个物品的容积为 j 的背包方案数

· 1.当$j-v[i] > 0$ 的时候，$f[i][j]$ 必然会包含选取了第 i 个物品所构成的一些方案，且在这些情况中，第 i 个物品必然只存在一个。那么，在$f[i][j] $中的这些状态必然是从$g[i][j-v[i]]$(不选i装满容积j-v[i])的状态下再拿了一个 i 构成的。

· 2.当$j-v[i]\leq0$的时候，$f[i][j]$ 中本来就不包含选取 i 这个物品的情况所以直接就是$f[i][j]$ 。

转移方程为：
$$
H(f)=\left\{\begin{matrix} g[i][j]=f[n][j]-g[i-1][j-v[i]]，j-v[i]>0\\
f[i][j]，j-v[i]\leq0 \end{matrix}\right.
$$
最后加上滚动数组优化就好了

3.代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=3e3+7;
int f[MAXN],g[MAXN],v[MAXN];
template <typename _TP>
inline void qread(_TP &X){
	char ch=0;int w;X=0;
	while(!isdigit(ch)){w=ch=='-';ch=getchar();}
	while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
	X=w?-X:X;
}
int main(){
	int n,m;
	qread(n);qread(m);
	for(int i=1;i<=n;i++){
		qread(v[i]);
	}
	f[0]=1;g[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=v[i];j--){
			f[j]=(f[j]+f[j-v[i]])%10;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j>=v[i])g[j]=(f[j]-g[j-v[i]]+10)%10;
			else g[j]=f[j];
			cout<<g[j];
		}
		cout<<"\n";
	}
	return 0;
}