题解 P5365 【[SNOI2017]英雄联盟】

· · 题解

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

题目右转：题目

更好的阅读，请戳我

首先我们仔细地看一下题目，题意是让我们在能让展示方案达到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;
}

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