@[x17875487211](/user/490694) ,能将详细描述下，什么初始化成-INF
by 鲨齿渊虹 @ 2022-09-25 18:43:09
@[鲨齿渊虹](/user/462965) dp数组呗
by Vergil_Sparda @ 2022-09-25 19:09:34
@[鲨齿渊虹](/user/462965) 你如果初始化为0就代表你有很多件价格为0但是有体积的“虚拟物品”，与你真实的物品组合起来其实真实物品花费不了那么多空间配合上虚拟物品也能达到很大的空间
先用最基础的01背包举例子
就比如说你有一件体积为2价值为5的物品
你更新一个一共可以转10体积的背包
如果初始化为0
那么dp[2]=dp[3]=...dp[10]=5
其实这时候dp[j]的定义是前i减物品，所占空间**不超过j**所能达到的最大价值，这其实是一个很容易被忽视的细节
而你初始化成-INF
只有dp[2]=3
这是因为你的dp[j]此时的定义是所占体积**正好是j**所能取得的最大价值
因此你的答案应该是最后再在dp数组扫一遍求最大值
这个细节造就了很多爆0的
再看到这题，你如果定义成新鲜值也不超过那个下标显然不合理，因为我们的新鲜值要求的是大于等于，如果我们用第二种，刚好等于下标的定义那么最后再用ans数组dp一遍就可以求大于等于的情况了
然后就是这题因为设置成刚好等于，但是又有新鲜值很大但是多多益善的情况，因此我们用最大的下标顺便存下超过要询问的最大新鲜值500的情况
贴个代码吧
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn=510;
int n,T,dp[maxn][maxn],ans[maxn][maxn];
signed main(){
scanf("%lld%lld",&n,&T);
memset(dp,-0x3f,sizeof(dp));
memset(ans,-0x3f,sizeof(ans));
int INF=dp[0][0];
dp[0][0]=0;
for(int i=1;i<=n;i++){
int co,fr,be;
scanf("%lld%lld%lld",&co,&fr,&be);
for(int j=500;j>=co;j--)
for(int k=500+fr;k>=fr;k--){
if(dp[j-co][k-fr]!=INF) dp[j][min(k,500ll)]=max(dp[j][min(k,500ll)],dp[j-co][k-fr]+be);
//printf("dp[%lld][%lld]=%lld\n",j,k,dp[j][k]);
}
}
for(int i=0;i<=500;i++)
for(int j=500;j>=0;j--){
ans[i][j]=max(i>=1?ans[i-1][j]:INF,max(dp[i][j],ans[i][j+1]));
}
while(T--){
int c,f;
scanf("%lld%lld",&c,&f);
printf("%lld\n",ans[c][f]==INF?0:ans[c][f]);
}
return 0;
}
```
by x17875487211 @ 2022-09-25 20:01:52
@[x17875487211](/user/490694) ，好的谢谢，%%%
by 鲨齿渊虹 @ 2022-09-26 19:18:05