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

· · 题解

这是一道标准的背包问题——

题目传送门

更好的阅读体验？

废话不多说，不会的童鞋们跟我来！Go!

1.逐步分析

既然是背包问题，最重要的当然就是转移方程了，所以转移方程是什么呢？

题中，我们知道了英雄的数量，每一种英雄的数量以及价值，没错，这就是所谓的多重背包。

当然，这道题不同的地方是，我们要求的是最少花费的钱数，所以我们不妨先在开始读入价钱的时候，将所有的价钱累加起来，算出最多需要花费的钱数，当作总钱数。

//读入部分
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>k[i];
for (int i=1;i<=n;i++) {
    cin>>c[i];
    qm+=c[i]*k[i];//累加  
}

而在转移方程中，我们可以用第一维表示取前 i 件物品，第二维表示花费 j Q币，即：

dp[i][j]=max(dp[i][j],dp[i][j-x*c[i]]*x);

其中，x 为取第 i 种物品的个数

而考虑到维度优化，根据传统的背包模板 经过思考，我们可以将第一维“取前几件物品”省略，即：

dp[j]=max(dp[j],dp[j-x*c[i]]*x);

对了，花0个Q币的方案数默认为1，即：

dp[0]=1;

2.AC代码及注释

#include<bits/stdc++.h>//万能明星头
using namespace std;
const int N=1000001;
long long n,m,k[N],c[N],qm,dp[N]={1},ans; 
//如题
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);//亲测优化程度基本大于快读
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>k[i];
    for (int i=1;i<=n;i++) {
        cin>>c[i];
        qm+=c[i]*k[i];  
    }//输入部分
    for (int i=1;i<=n;i++){//枚举前i件物品
        for (int j=qm;j>=0;j--){//倒序枚举花j个Q币
            for (int x=0;x<=k[i]&&x*c[i]<=j;x++){//枚举买x个皮肤
                dp[j]=max(dp[j],dp[j-x*c[i]]*x);//转移方程
            }
        }
    }
    while (ans<=qm&&dp[ans]<m) ans++;//满足条件就++
    cout<<ans<<endl;//输出
    return 0;//好习惯要保持
}

3.完结撒花！

本次题解就这么愉快地结束啦！感谢您坚持看到了最后！

如果还有什么不懂的问题，欢迎在评论区回复哦，我会第一时间解答哒！

当然，如果您看懂了，就点个赞纪念一下您的成长吧！