SpellCardsEasy
SRM 563 · 2012-06-05 · by cgy4ever
SRM 563 · 2012-06-05 · by cgy4ever · Dynamic Programming
Problem Statement
Problem Statement
You are playing a card game.
In the card game, each card holds a magic spell with two properties: its level and its damage.
During the game, you will play some of the cards (possibly none or all of them) to attack your enemy.
Initially, there are n cards. The cards are placed in a row and they are labeled from 0 to n-1, in order. You are given twoint[] s: level and damage.
For each i, the level of card i is level[i], and its damage is damage[i].
In each turn of the game, you can pick a card to play. You can only pick card i if there are at least another (level[i]-1) cards to the right of it. Picking a card with level L and damage D has the following effects:
Return the maximal total damage you can deal to your opponent.
Initially, there are n cards. The cards are placed in a row and they are labeled from 0 to n-1, in order. You are given two
In each turn of the game, you can pick a card to play. You can only pick card i if there are at least another (level[i]-1) cards to the right of it. Picking a card with level L and damage D has the following effects:
- Your opponent receives D damage.
- Starting with this card, L cards are discarded. That is, if the chosen card was card i, then the discarded cards are cards i to (i+L-1), inclusive.
Return the maximal total damage you can deal to your opponent.
Constraints
- level will contain between 1 and 50 elements, inclusive.
- level and damage will contain the same number of elements.
- Each element in level will be between 1 and 50, inclusive.
- Each element in damage will be between 1 and 10,000, inclusive.
Examples
0)
{1,1,1}
{10,20,30}
Returns: 60
You can use all three spell cards (in any order), so the total damage is: 10 + 20 + 30 = 60.
1)
{3,3,3}
{10,20,30}
Returns: 10
You are only allowed to use card 0. Using it deals 10 damage and discards all three cards.
2)
{4,4,4}
{10,20,30}
Returns: 0
This time you can't use any spell cards.
3)
{50,1,50,1,50}
{10,20,30,40,50}
Returns: 60
You can use the spell cards with damage 20 and 40.
4)
{2,1,1}
{40,40,10}
Returns: 80
Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SpellCardsEasy with a public method int maxDamage(vector<int> level, vector<int> damage) · 120 test cases · 2 s / 256 MB per case