题解_LUOGU_P4141消失之物
题意:
ftiasch 有 n 个物品, 体积分别是 w 1 , w 2 , … , w n w_1,w_2,\dots,w_n w1,w2,…,wn。由于她的疏忽，第 i个物品丢失了。
“要使用剩下的 n-1 物品装满容积为 x 的背包，有几种方法呢？”——这是经典的问题了。
她把答案记为 cnt ( i , x ) \text{cnt}(i,x) cnt(i,x) ，想要得到所有 i ∈ [ 1 , n ] , x ∈ [ 1 , m ] i \in [1,n], x \in [1,m] i∈[1,n],x∈[1,m] 的 cnt ( i , x ) % 10 \text{cnt}(i,x)\%10 cnt(i,x)%10 表格。
思路：
很显然，可以轻松地求出使用所有物品装满容积 j 的方案数
f [ i ] [ j ] f[i][j] f[i][j]表示使用前 i 个物品的容积为 j 的背包方案数
令 g [ i ] [ j ] g[i][j] g[i][j]表示不使用第 i 个物品的容积为 j 的背包方案数
转移方程为：
H
(
f
)
=
{
g
[
i
]
[
j
]
=
f
[
n
]
[
j
]
−
g
[
i
−
1
]
[
j
−
v
[
i
]
]
，
j
−
v
[
i
]
>
0
f
[
i
]
[
j
]
，
j
−
v
[
i
]
≤
0
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.
H(f)={g[i][j]=f[n][j]−g[i−1][j−v[i]]，j−v[i]>0f[i][j]，j−v[i]≤0
也就是:
- 当 j − v [ i ] > 0 j-v[i] > 0 j−v[i]>0 的时候， f [ i ] [ j ] f[i][j] f[i][j] 必然会包含选取了第 i 个物品所构成的一些方案，且在这些情况中，第 i 个物品必然只存在一个。那么，在$f[i][j] 中 的 这 些 状 态 必 然 是 从 中的这些状态必然是从 中的这些状态必然是从g[i][j-v[i]]$(不选i装满容积j-v[i])的状态下再拿了一个 i 构成的。
- 当 j − v [ i ] ≤ 0 j-v[i]\leq0 j−v[i]≤0的时候， f [ i ] [ j ] f[i][j] f[i][j] 中本来就不包含选取 i 这个物品的情况所以直接就是 f [ i ] [ j ] f[i][j] f[i][j]
最后加上滚动数组优化就好了
代码：
#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;
}