@[Error_Eric](/user/217300) 呃，我没太理解为什么要初始化-inf
by Kniqht @ 2022-09-24 12:40:06
先贴一发已经 AC 的。
```cpp
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
void readln(int &I){
I=0;char C=getchar();bool f=0;
while (!isdigit(C))f|=(C=='-'),C=getchar();
while ( isdigit(C))(I*=10)+=(C-'0'),C=getchar();
if(f)I=-I;
}
int n,q,cj,fj;
int co[505],fr[505],w[505];
long long f[505][505],g[505][505];
const long long inf=0x3fffffffffffffff;
int main(){
readln(n),readln(q);
for(int i=1;i<=n;i++)
readln(co[i]),readln(fr[i]),readln(w[i]);
for(auto&fx:f)for(auto&fxx:fx)fxx=-inf;
for(auto&gx:g)for(auto&gxx:gx)gxx=-inf;
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=500;j>=co[i];j--){
for(int k=501+fr[i];k>=fr[i];k--){
f[j][min(501,k)]=max(f[j][min(501,k)],f[j-co[i]][k-fr[i]]+w[i]);
}
}
}
for(int i=0;i<=500;i++)
for(int j=501;j>=0;j--)
if(i==0)g[i][j]=max(f[i][j],g[i][j+1]);
else g[i][j]=max(f[i][j],max(g[i-1][j],g[i][j+1]));
while (q--)
readln(cj),readln(fj),printf("%lld\n",max(g[cj][fj],0ll));
}
```
by Error_Eric @ 2022-09-24 12:40:24
@[qi136](/user/315205) 恰好背包是要初始化 -inf 的。
例如一个商品价格是 $3$，价值是 $4$，你初始 $f[2]$ 是 $0$ ， $f[5]$ 可能会被赋值为 $4$。
by Error_Eric @ 2022-09-24 12:41:46
@[Error_Eric](/user/217300) 哦，明白了
by Kniqht @ 2022-09-24 12:42:30
@[ETO_leader](/user/388691) 我没有看出来你的做法是啥。请仔细阅读题意。
by Error_Eric @ 2022-09-24 12:46:31
剩下的人已经私信回了。
by Error_Eric @ 2022-09-24 12:46:51
@[Error_Eric](/user/217300) 蟹蟹 DL
by JackMerryYoung @ 2022-09-24 12:50:48
```cpp
#include "iostream"
using namespace std;
#include "cmath"
struct flu
{
int cost,be,fr;
}s[503];
int n,m;
int be,sfre,scost,maxbe,ccost,cfre;
void dfs(int i,int cost,int fre)
{
if((s[i].cost+scost>cost)||i>n-1)
{
if(sfre>=fre)
{
maxbe=max(maxbe,be);
}
return;
}
if(s[i].cost+scost<cost)
{
scost+=s[i].cost,
be+=s[i].be,
sfre+=s[i].fr,
dfs(i+1,cost,fre),
scost-=s[i].cost,
be-=s[i].be;
sfre-=s[i].fr;
}
dfs(i+1,cost,fre);
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>s[i].cost>>s[i].fr>>s[i].be;
for(int i=0;i<m;i++)
{
cin>>ccost>>cfre;
be=0,sfre=0,scost=0,maxbe=0;
dfs(0,ccost,cfre);
cout<<maxbe<<endl;
}
}//求助为啥dfs不行（能过样例
```
by isxi @ 2022-09-24 12:53:56
@[AKimizuss](/user/681982) 别问了，正解不香吗...
by JackMerryYoung @ 2022-09-24 12:58:22
dp求看
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510;
int n, q;
int cst, be, fr;
int dp[N][N];
int main(){
// memset(dp, -0x3f, sizeof dp);
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++ i){
scanf("%d%d%d", &cst, &fr, &be);
for(int j = 500; j >= 0; -- j){
for(int k = 500; k >= 0; -- k){
if(j - cst >= 0 && k - fr > 0){
dp[j][k] = max(dp[j][k], dp[j - cst][k - fr] + be);
dp[j][k] = max(dp[j][k], dp[j][k + 1]);
}
else if(j - cst >= 0 && k - fr <= 0) {
dp[j][k] = max(dp[j][k], dp[j - cst][0] + be);
dp[j][k] = max(dp[j][k], dp[j][k + 1]);
}
}
}
}
for (int i = 1; i <= 500; i++) {
for (int j = 500; j >= 0; j--)
dp[i][j] = max(dp[i][j], dp[i][j + 1]);
}
for(int i = 1; i <= q; ++ i){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", dp[a][b]);
}
}
```
by aaaaaaaawsl @ 2022-09-24 13:05:27