【回退背包】AT2346 [ARC070B] No Need
ldkldk
·
·
个人记录
https://www.luogu.com.cn/problem/AT2346
刚开始没注意k<=5000，死想想不出，结果瞄了一眼题解...
那不直接把大于k的a全部删了不就行了？
~~气死偶列~~
警示后人
然后赶紧返回来想，结果发现其实是个很简单的技巧。也就是回退背包。
我们可以考虑先全局做一个背包，然后考虑每一个物品消失后对答案的影响。
这也就是说，假设当前价值为val，$f[i]-=f[i-val]$（注意要正过来做）
然后找一遍可能转移到大于k的f就做完了
本题不难，只是想总结有这么一个叫回退背包的东西
代码（B题都挂了没救了没救了）：
```cpp
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,k,N,ans,a[5005],b[5005],f[5005];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]<=k)b[++N]=a[i];
}
f[0]=1;
for(int i=1;i<=N;i++){
for(int j=k;j>=b[i];j--){
f[j]+=f[j-b[i]];
}
}
for(int i=1;i<=N;i++){
for(int j=b[i];j<=k;j++){
f[j]-=f[j-b[i]];
}
bool pd=0;
for(int j=k-b[i];j<k;j++){
if(f[j]){
pd=1;
break;
}
}
if(!pd)ans++;
for(int j=k;j>=b[i];j--){
f[j]+=f[j-b[i]];
}
}
cout<<ans<<endl;
return 0;
}
```