洛谷P4141 消失之物 题解

题目链接：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)\) 表格。

只需要输出末位数字。

设 \(f[i][j]\) 为只用前 \(i\) 件物品，不考虑删除任何物品时，恰好装满容量为 \(j\) 的背包的方案数，显然有 \[ f[i][j]=f[i-1][j]+f[i-1][j-w[i]] \] 滚动数组一下就是

f[0]=1;
for(int i=1; i<=n; i++)
	for(int j=m; j>=w[i]; j--)
		f[j]+=f[j-w[i]];

那么现在求出来的 \(f[i]\) 也就是原来的 \(f[n][i]\) 了

于是设 \(g[i][j]\) 为不考虑物品 \(i\) 的贡献恰好装满容量为 \(j\) 的背包的方案数

首先容易想到一个看起来正确的柿子（其实是错的） \[ g[i][j]=f[n][j]-f[n][j-w[i]] \] 为什么错呢？因为 \(f[n][j-w[i]]\) 中也可能含有 \(w[i]\) 的贡献！

那么其实稍微改一改就对了 \[ g[i][j]=f[n][j]-g[i][j-w[i]] \] 此时的 \(g[i][j-w[i]]\) 恰好删除了物品 \(i\) 的贡献，不错

注意这个 \(g[i][j]\) 需要 \(j\) 顺推，因为我们需要 \(g[i][j-w[i]]\)

然后这个柿子还是不够精简

注意到我们其实并不需要记录 \(i\) 这一状态，因为我们其实不需要保存这些信息

加上之前的滚动数组优化，柿子可以化简为 \[ g[j]= \begin{cases} f[j]-g[j-w[i]],&j \ge w[i], \\f[j],&\text{default.} \end{cases} \] 嗯，其实还可以化简。

memcpy(g,f,sizeof(f));
for(int j=w[i]; j<=m; j++)
	g[j]-=g[j-w[i]];

时间复杂度 \(O(nm)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
int n,m;
int w[N],f[N],g[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    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++)
    {
        memcpy(g,f,sizeof(f));
        for(int j=w[i]; j<=m; j++)
            g[j]=(g[j]-g[j-w[i]])%10;
        for(int j=1; j<=m; j++)
            cout <<(g[j]+10)%10; // +10是防止出现负结果
        cout << '\n';
    }
    return 0;
}