题解：P11377 [GESP202412 七级] 武器购买

题目意思概括：

t组数据，对于每组数据

n

个物品无法在

Q

价钱让总强度

> P

思路：背包

1.判断类型

根据样例显然是01背包

2.推导转移方程

(1)让

dp_i

为花费为

i

时最大总强度为

dp_i

c[i]

为花费按照思路所以

这时方程为

dp_j=max(dp_j,dp_{j-c[i]}+p[i])

背包代码如下

CPP

for(int i=1;i<=n;i++)//背包 
{
		for(int j=Q;j>=c[i];j--)
		{
			dp[j]=max(dp[j],dp[j-c[i]]+p[i]);
		}
	}

完整代码如下

温馨提示多测要清空

CPP

#include<bits/stdc++.h>//具体解析见上 
using namespace std;
int t,n,P,Q;
int p[50500],c[50500],dp[50500];//开大点数组好习惯 
int main()
{
	ios::sync_with_stdio(false);//同步 输入输出减少一些时间 
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>P>>Q;
		for(int i=1;i<=n;i++)
		{
			cin>>p[i]>>c[i];
		}
		memset(dp,0,sizeof(dp));//多测清空
		for(int i=1;i<=n;i++)//背包 
		{
			for(int j=Q;j>=c[i];j--)
			{
				dp[j]=max(dp[j],dp[j-c[i]]+p[i]);
			}
		}
		if(dp[Q]<P) cout<<"-1\n";//输出
		else 
		{
			for(int i=1;i<=Q;i++)//正序寻找ans 
			{
				if(dp[i]>=P)
				{
					cout<<i<<'\n';
					break;
				}
			}
		}
	}

	return 0;
}

本蒟蒻第一篇题解求过

题解：P11377 [GESP202412 七级] 武器购买

文章操作

相关推荐

评论

题解：P11377 [GESP202412 七级] 武器购买