同问，80pts
by Nicrobot @ 2022-09-24 12:24:21
您这个是不是应该是新鲜程度最大为 $f_j$（
by dbxxx @ 2022-09-24 12:24:23
考虑恰好费用二维费用 01 背包。
注意特判总新鲜度大于要求新鲜度上界情况。
by Error_Eric @ 2022-09-24 12:27:48
@[Error_Eric](/user/217300)
0 pts 代码求调
``` cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int
int N, Q;
int cost[505], fresh[505], beautiful[505];
int f[505][25005];
signed main()
{
scanf("%d%d", &N, &Q);
for(int i = 1; i <= N; ++ i)
scanf("%d%d%d", &cost[i], &fresh[i], &beautiful[i]);
for(int i = 1; i <= N; ++ i)
{
for(int j = 500; j >= cost[i]; -- j)
{
for(int k = 500; k >= fresh[i]; -- k)
{
f[j][k] = max(f[j][k], f[j - cost[i]][k - fresh[i]] + beautiful[i]);
}
}
}
// for(int j = 0; j <= 10; ++ j)
// {
// for(int k = 0; k <= 20; ++ k)
// {
// cout << f[j][k] << ' ';
// }
// puts("");
// }
for(int i = 1; i <= Q; ++ i)
{
int ci, fi;
scanf("%d%d", &ci, &fi);
int maxn = -1;
for(int j = fi; j <= 500; ++ j)
maxn = max(maxn, f[ci][j]);
printf("%d\n", maxn);
}
return 0;
}
```
by JackMerryYoung @ 2022-09-24 12:30:49
@[Error_Eric](/user/217300) 求问判了上界但是 80pts。
谢谢
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, q;
int co[N], be[N], fr[N];
int read() {
int x = 0, o = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') o = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * o;
}
int dp[N][N]; // 价格，新鲜度
int main() {
//freopen("buy.in", "r", stdin);
//freopen("buy.out", "w", stdout);
n = read();
q = read();
for (int i = 1; i <= n; i++) {
co[i] = read();
fr[i] = read();
be[i] = read();
}
for (int i = 1; i <= 500; i++)
for (int j = 1; j <= 500; j++)
dp[i][j] = -1e9;
for (int i = 1; i <= 500; i++) dp[0][i] = -1e9;
for (int i = 1; i <= n; i++) {
for (int j = 500; j >= co[i]; j--) {
for (int k = 500; k >= fr[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - co[i]][k - fr[i]] + be[i]);
for (int k = 500; k >= 500 - fr[i] + 1; k--) // 新鲜度大于部分
dp[j][500] = max(dp[j][500], dp[j - co[i]][k] + be[i]);
}
}
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 <= 500; i++) {
for (int j = 0; j <= 500; j++)
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
while (q--) {
int c = read(), f = read();
printf("%d\n", dp[c][f] < 0 ? 0 : dp[c][f]);
}
return 0;
}
```
by Nicrobot @ 2022-09-24 12:32:15
我 tm 也挂分了啊...
我先调下自己的（悲）
by Error_Eric @ 2022-09-24 12:34:38
0pts求调（感觉我没理解题意，样例没过）
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,cost[100005],fr[100005],be[100005],c[100005],f[100005];
ll dp[5000][5000],cnt=0;
int main(){
ios::sync_with_stdio(false);
cin>>n>>q;
for (ll i=1;i<=n;i++) cin>>cost[i]>>fr[i]>>be[i];
for (ll i=1;i<=q;i++) cin>>c[i]>>f[i];
for (ll a=1;a<=q;a++){
ll v=c[a];
ll m=f[a];
for (ll i=1;i<=n;i++){
for (ll j=v;j>=cost[i];j--){
for (ll k=m;k>=fr[i];k--){
dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-fr[i]]+be[i]);
}
}
}
cnt+=dp[v][m];
}
cout<<cnt<<endl;
return 0;
}
```
by ETO_leader @ 2022-09-24 12:36:13
@[JackMerryYoung](/user/224558) 费用珂能小于ci吧。。。这个f是恰好费用的
by Kniqht @ 2022-09-24 12:36:26
@[qi136](/user/315205) 他没有初值 -inf 是 01 费用。
by Error_Eric @ 2022-09-24 12:39:35
@[ETO_leader](/user/388691) 你这个不仅复杂度爆炸，也没考虑新鲜度大于f的情况，也没考虑花的钱小于c的情况。。。
by Kniqht @ 2022-09-24 12:39:37