Editorial for New Year's '17 P6 - Christmas Cards - Olympiads Online Judge

Editorial for New Year's '17 P6 - Christmas Cards

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This problem is a straightforward dynamic programming problem. The two states for the problem are $dp[\text{current card}][\text{maximum card}]$ . First, you must make the observation that cards in any solution will always be played in the order they are found in the deck. The current card is the card that you are deciding whether or not to play. The maximum card is the highest card that you can play. For each state, you either do not play the card ( $dp[\text{current}+1][\text{maximum}]$ ~dp[\text{current}+1][\text{maximum}]~), or you do play the card ( $dp[\text{current}+1][\text{maximum}+d[i]]+c[i]$ ).

Time Complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

Comments

There are no comments at the moment.