题解：P8548 小挖的买花

· · 题解

前言：

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

题意：

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

思路：

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

dp_{i,j}=\max(dp_{i,j},dp_{i-cost_k,j-fr_k}+be_k)

其中的 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;
 }