HBC24870PokemonUltraSun(评测),动态规划,概率dp[USACO 2009 Dec G]Video Game Troubles题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

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 and games that helps his cows produce the most milk and thus nourish the most children.

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

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC24870PokemonUltraSun(评测) 动态规划 概率dp[USACO 2009 Dec G]Video Game Troubles题解