自动搬运

查看原文

来自洛谷，原作者为

	LemonChay **

搬运于2025-08-24 22:10:02，当前版本为作者最后更新于2019-10-02 08:18:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看着这道题目没有什么人写题解，那我就来一篇...

题目右转：题目

更好的阅读，请戳我

首先我们仔细地看一下题目，题意是让我们在能让展示方案达到M种的情况下花费最少的钱，这就让我情不自禁地想到了背包问题，那么是什么背包呢？

在接着看，对于每一个皮肤，都有一个数量、一个购买的Q币数(花费)，那么这种有限物品数量的背包问题就是多重背包问题了。

根据题目要求的量，我们来设计状态。我们看到，方案数量是价值，Q币数量是我们的花费，于是我们用dp[i][j]来表示前i个皮肤的j个花费的最大方案数

分析到这里，我们大致地可以把状态转移方程给求出来了：

dp[i][j]=max(dp[i][j],dp[i−1][j−p∗c[i]]∗p)

其中p是当前英雄选的皮肤数量，c[i]是题目中的意思。

如果二维数组的内存太大，给人一种 心慌慌 的感觉，那么不妨再分析一下，如何用一维数组来表示状态。

我们看到，方案数量是根据花费的变化而变化的；换句话说，M和i是没有什么太大的关系。那么我们这么来表示状态：dp[j]表示花费j个Q币的最大方案数量。借鉴二维的状态转移方程，我们 很容易 地得到一维地状态转移方程：

dp[j]=max(dp[j−p∗c[i]]∗p,dp[j])

到这里，我们分析的差不多了。核心部分已经解决了，那么细节就自己去抠吧。

来，上代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
long long int dp[1000001];//状态数组
long long int k[1000001],c[1000001];//数组意义如题目所述
long long int n,m,qb;
int main()
{
	int i,j,p;
	cin>>n>>m;
	for(i=1;i<=n;i++)//输入
	{
		cin>>k[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>c[i];
		qb+=c[i]*k[i];//将Q币总量记录下来
	}
	dp[0]=1;//初始化
	for(i=1;i<=n;i++)//枚举皮肤的种类
	{
		for(j=qb;j>=0;j--)//枚举每一“格”Q币数量
		{
			for(p=0;p<=k[i]&&p*c[i]<=j;p++)//枚举当前皮肤的数量
			{
				dp[j]=max(dp[j],dp[j-p*c[i]]*p);//
状态转移方程
			}	
		}
	}
	long long int ans=0;
	while(ans<=qb&&dp[ans]<m) ans++;//找到最小、同时大于M的那一“格”Q币数量
	cout<<ans;
	return 0;
}

第一篇题解，希望管理员通过