自动搬运

查看原文

来自洛谷，原作者为

	Dark_Knight_AK_ALL CSP-J/S不拿一等不改签||||知耻而后勇。||时空是个圆圈，直行或是转弯，我们最终都会相见。||挂分大师

搬运于2025-08-24 22:40:03，当前版本为作者最后更新于2025-08-19 12:28:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：

老师在模拟赛里放了这题，所以写篇题解。

题意：

给你每朵花的购买费用，新鲜度以及美丽值。每次询问输入一个新鲜值的限制以及费用的限制。要求选出来的几朵花的总费用不超过限制，新鲜度要大于限制。

思路：

考虑背包。设 $dp_{i,j}$ 表示花的费用为 $i$，新鲜度为 $j$，所能达到的最大的美丽值。那么可以得到转移

其中的 $k$ 代表当前枚举到的花朵。注意到是从前往后转移，因此要从后往前枚举。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,cost[511],fr[511],be[511],dp[511][511];
int c,f;
signed main()
{ 
	cin>>n>>q;
	for(int i=0;i<=500;i++)
		for(int j=1;j<=500;j++)dp[i][j]=INT_MIN;
	for(int i=1;i<=n;i++)cin>>cost[i]>>fr[i]>>be[i];
	for(int i=1;i<=n;i++)
		for(int j=500;j>=0;j--)
			for(int l=500;l>=0;l--)
			if(j>=cost[i])
			dp[j][l]=max(dp[j][l],dp[j-cost[i]][max(l-fr[i],0ll)]+be[i]);
	while(q--)
	{
		cin>>c>>f;
		cout<<max(0ll,dp[c][f])<<endl;
	}
	return 0;
 }