洛谷 P5365 [SNOI2017] 英雄联盟

发布时间:2024年01月24日

题目描述

分析

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

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

剩下的基本上就是一个多重背包模板了,转移方程( k k k 为选的物品数量):

d p i , j = max ? ( d p i , j , d p i ? 1 , j ? k × c i × k ) dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-k\times c_i}\times k) dpi,j?=max(dpi,j?,dpi?1,j?k×ci??×k)

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

注意

  • long long!!!
  • d p 0 dp_0 dp0? 要设为 1 1 1

代码

#include <bits/stdc++.h>
#define debug puts("Y")
#define inf 0x3f3f3f3f
#define int long long

using 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;
}
文章来源:https://blog.csdn.net/zc2000911/article/details/135824373
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。