NC24870 [USACO 2009 Dec G]Video Game Troubles
2022/8/14 6:22:48
本文主要是介绍NC24870 [USACO 2009 Dec G]Video Game Troubles,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目
题目描述
Farmer John's cows love their video games! FJ noticed that after playing these games that his cows produced much more milk than usual, surely because contented cows make more milk.
The cows disagree, though, on which is the best game console. One cow wanted to buy the Xbox 360 to play Halo 3; another wanted to buy the Nintendo Wii to play Super Smash Brothers Brawl; a third wanted to play Metal Gear Solid 4 on the PlayStation 3. FJ wants to purchase the set of game consoles (no more than one each) and games (no more than one each -- and within the constraints of a given budget) that helps his cows produce the most milk and thus nourish the most children.
FJ researched N (1 <= N <= 50) consoles, each with a console price Pi (1 <= Pi <= 1000) and a number of console-specific games Gi (1 <= Gi <= 10). A cow must, of course, own a console before she can buy any game that is specific to that console. Each individual game has a game price GPj (1 <= GPj price <= 100) and a production value (1 <= PVj <= 1,000,000), which indicates how much milk a cow will produce after playing the game. Lastly, Farmer John has a budget V (1 <= V <= 100,000) which is the maximum amount of money he can spend. Help him maximize the sum of the production values of the games he buys.
Consider one dataset with N=3 consoles and a V=$800 budget. The first console costs $300 and has 2 games with cost $30 and $25 and production values as shown: Game # Cost Production Value 1 $30 50 2 $25 80 The second console costs $600 and has only 1 game: Game # Cost Production Value 1 $50 130 The third console costs $400 and has 3 games: Game # Cost Production Value 1 $40 70 2 $30 40 3 $35 60 Farmer John should buy consoles 1 and 3, game 2 for console 1, and games 1 and 3 for console 3 to maximize his expected production at 210: Production Value Budget: $800 Console 1 -$300 Game 2 -$25 80 Console 3 -$400 Game 1 -$40 70 Game 3 -$35 60 ------------------------------------------- Total: 0 (>= 0) 210
输入描述
- Line 1: Two space-separated integers: N and V
- Lines 2..N+1: Line i+1 describes the price of and the games ?available for console i; it contains: Pi, Gi, and Gi pairs of space-separated integers GPj, PVj
输出描述
- Line 1: The maximum production value that Farmer John can get with his budget.
示例1
输入
3 800 300 2 30 50 25 80 600 1 50 130 400 3 40 70 30 40 35 60
输出
210
题解
知识点:背包dp。
分组背包套01背包,因为每组物品不能枚举否则超时。
要先开一个临时空间给分组背包内的01背包,因为组内物品是一同考虑的,不能影响一个组的值,最后和原数组没有买游戏机的比较取最大值。
剩下的看代码和01背包差不多。
时间复杂度 \(O(nvg)\)
空间复杂度 \(O(v)\)
代码
#include <bits/stdc++.h> using namespace std; int dp[100007], tmp[100007]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, v; cin >> n >> v; for (int i = 1, p, g;i <= n;i++) {///组 cin >> p >> g; for (int k = p;k <= v;k++) tmp[k] = dp[k - p];///买游戏机 for (int j = 1, gp, pv;j <= g;j++) { ///游戏 cin >> gp >> pv; for (int k = v;k >= p + gp;k--)///因为买了游戏机,价格不能小于游戏机加这个游戏 tmp[k] = max(tmp[k], tmp[k - gp] + pv);///在第i组滚动 } for (int k = p;k <= v;k++) dp[k] = max(dp[k], tmp[k]);///和不买游戏机比 } cout << dp[v] << '\n'; return 0; }
这篇关于NC24870 [USACO 2009 Dec G]Video Game Troubles的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享
- 2024-04-14shell 正则判断字符串内是否含有th-icode9专业技术文章分享