题解：P1899 魔法物品

Just_Starlet · 2025-07-29 16:43:41 · 题解

一篇贪心+dp好题，总结了讨论区、题解区一些注意点，写了这篇文章（不喜勿喷）。

题目分析

• 先考虑普通物品，没有大作用，可以直接卖掉。
• 再考虑魔法物品，
  如果 b_i-p \le a_i（鉴定反而倒亏钱），这种可以称为假魔法物品，当普通物品卖了就行。

:::::info[细节（有关于输入输出的一点实现）]{open}

其实没必要手写输入函数。

通过数字后跟的是 空格 还是 \n 即可。

::::info[伪代码]{open}

  scanf("%d",&x);
  if(getchar()==' '){
    scanf("%d",&y);
      ...//魔法物品
  }
  else{
    ...//普通物品
  }

:::: :::warning[数据问题]{open} 这题的数据好像有锅，有格外的 \r ，详见这个帖子。 ::: ::::: 进一步而言：

• 直接贪心地卖掉普通物品和加魔法物品作为启动资金 pre。
• 若 pre \ge p，那么直接累加所有魔法物品的鉴定后价格即可。
• 若 pre<p，那就得靠 dp 了。

记 profit_i=b_i-a_i-p 为第 i 件魔法物品鉴定的纯利润。

定义 f_i 为凑够 i 元最少的损失纯利润。

那么

（此处数组下标为 \max(0,i-a_j)，是为了防止数组越界。）
边界条件： f_0=0

最终答案就是 ans=pre+\sum\limits_{j=0}^{n}(b_j-p)-f_{p-pre}。 ::::success[然后你就可以欢乐的AC这题了]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 114514191
#define N 100005
int a[N],pro[N],f[N];
int n,p,pre=0,suma=0,profits=0,cnt=0;
char ch;
int main(){
    scanf("%d %d",&n,&p);
    int x,y;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ch=getchar();
        if(ch!=' ') pre+=x;
        else{
            scanf("%d",&y);
            if(y-x<=p) pre+=x;
            else{
                suma+=x;
                a[++cnt]=x;
                pro[cnt]=y-p-x;
                profits+=pro[cnt];
            } 
        }
    } 
    if(pre>=p){
        printf("%d\n",suma+pre+profits);
        return 0;
    }
    if(suma+pre<p){
        printf("%d\n",suma+pre);
        return 0;
    }
    int lft=p-pre;f[0]=0;
    for(int j=1;j<=lft;j++) f[j]=INF;
    for(int i=1;i<=cnt;i++)
        for(int j=lft;j>=0;j--){
            f[j]=min(f[j],f[max(0,j-a[i])]+pro[i]);
        } 
    printf("%d\n",pre+profits+suma-f[lft]);
    return 0;
}

请不要直接用 Ctrl+C 与 Ctrl+V 噢