Editorial for VMSS Pre-Pre-Windsor P7 - Magical Bribery

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.

Author: AQT

This is a dynamic programming problem.

Let $dp[i]$ ~dp[i]~ represent the maximum value for $i$ ~i~ cards.

To get $dp[i]$ ~dp[i]~, we can try every package size.

More formally, you're trying to find a $j$ ~j~ such that it maximizes $dp[i-j] + N_j$ ~dp[i-j] + N_j~.

The base case is when $dp[0] = 0$ ~dp[0] = 0~.

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

Memory Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.