洛谷 P5365 [SNOI2017] 英雄联盟

本文主要是介绍洛谷 P5365 [SNOI2017] 英雄联盟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

分析

这题很容易给人带来不是背包的错觉。

设状态 $d{p}_{i,j}$ 表示前 $i$ 个英雄花费 $j$ 元买皮肤的最大方案数，而背包容量就是所有英雄的 $k_i\times t_i$ 之和。

剩下的基本上就是一个多重背包模板了，转移方程（$k$ 为选的物品数量）：

$$d{p}_{i,j}=\max (d{p}_{i,j},d{p}_{i-1,j-k\times c_i}\times k)$$。

这里之所以要乘 $k$ 是因为如果选了 $k$ 个那么这 $k$ 个皮肤每个都可以跟前面的方案匹配，获取答案是枚举最少的钱数使得方案数不小于 $m$ 即可，当然这里可以用滚动数组优化到 $1$ 维。

注意

• 开 long long！！！
• $d{p}_0$ 要设为 $1$。

代码

#include <bits/stdc++.h>
#define debug puts("Y")
#define inf 0x3f3f3f3f
#define int long longusing namespace std;typedef long long ll;
const int N = 5 * 1e5 + 5;
int n, m, V, K[N], c[N], dp[N];signed main() {cin >> n >> m;for (int i = 1; i <= n; i ++) {cin >> K[i];} for (int i = 1; i <= n; i ++) {cin >> c[i];V += K[i] * c[i];}dp[0] = 1;for (int i = 1; i <= n; i ++) {for (int j = V; j >= 0; j --) {for (int k = 0; k <= K[i]; k ++) {if (j >= k * c[i]) {dp[j] = max(dp[j], dp[j - k * c[i]] * k);}}}}int now = 0;for (; now <= V && dp[now] < m; now ++) {}cout << now;return 0;
}

这篇关于洛谷 P5365 [SNOI2017] 英雄联盟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---