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] represent the maximum value for i cards.

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

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

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

Time Complexity: \mathcal O(N^2)

Memory Complexity: \mathcal O(N)


Comments

There are no comments at the moment.