题解：P1899 魔法物品

Sunrise_beforeglow · 2025-03-07 17:22:20 · 题解

首先我们考虑普通物品，由于普通物品不用做决定。所以直接卖了它即可。

然后我们考虑魔法物品，如果这个物品鉴定后的价值减去鉴定卷轴的价格比它的鉴定前的价值还小，那么直接看作普通物品即可。

那么分类讨论，如果我手上的钱已经够买鉴定卷轴了，那么每个剩下的物品都可以获得鉴定后的价值减去鉴定卷轴的价格。

否则我们就要动态规划，我们定义 dp_i 表示使我有 i 元的最小亏损价格。

那么对于每个物品 x，令 a_x 表示它鉴定前的价格，b_x 表示它鉴定后的价格。

那么我们如果按鉴定前的价格卖出 x，会获得 a_i 元，但是会在之后少得到 b_i-P 元，所以它的亏损价格就是 b_i-P-a_i。然后我们直接看成背包问题即可。

注意当我卖掉所有的物品都不够买鉴定卷轴时那答案就是所有普通物品价格加上所有魔法物品鉴定前的价格。

#include <bits/stdc++.h>
using namespace std;
int n,p,x[5005],y[5005],sum,dp[5005],s;
vector<pair<int,int>>v;
int main()
{
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        char ch=getchar();
        if(ch==' ')
        {
            cin>>y[i];
            if(y[i]-p<=x[i])sum+=x[i];
            else v.push_back(make_pair(x[i],y[i])),s+=x[i];
        }
        else sum+=x[i];
    }
    if(sum>=p)
    {
        int ans=sum;
        for(auto i:v)ans+=i.second-p;
        cout<<ans;
        return 0;
    }
    for(int i=sum+1;i<=p;i++)dp[i]=2e9;
    s=sum;
    for(auto i:v)sum+=i.second-p,s+=i.first;
    for(auto i:v)
    {
        for(int j=p;j>=i.first;j--)
        {
            dp[j]=min(dp[j],dp[j-i.first]-i.first-p+i.second);
        }
    }
    if(dp[p]==2e9)cout<<s;
    else cout<<sum-dp[p];
    return 0;
}