洛谷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;
}