题解：P1899 魔法物品

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

题目分析

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

细节（有关于输入输出的一点实现）

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

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

伪代码

CPP

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

数据问题

这题的数据好像有锅，有格外的 \r ，详见这个帖子。

进一步而言：

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

记

profit_i=b_i-a_i-p

为第

i

件魔法物品鉴定的纯利润。

定义

f_i

为凑够

i

元最少的损失纯利润。

那么

f_i=\min\limits_{j=0}^{n} \{f_{\max(0,i-a_j)}+profit_j\}

（此处数组下标为

\max(0,i-a_j)

，是为了防止数组越界。）
边界条件：

f_0=0

最终答案就是

ans=pre+\sum\limits_{j=0}^{n}(b_j-p)-f_{p-pre}

。

然后你就可以欢乐的AC这题了

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243#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 噢

题解：P1899 魔法物品

文章操作

题目分析

相关推荐

评论

题解：P1899 魔法物品