Editorial for DMOPC '17 Contest 1 P4 - Quests


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: r3mark

For subtask 1, brute-force all possible choices of NPCs. After checking the gold and time obtained from reaching the NPC, the problem becomes unbounded knapsack.

Time complexity: \mathcal{O}(2^NNH)

For subtask 2, the problem is exactly unbounded knapsack.

Time complexity: \mathcal{O}(NH)

For the final subtask, consider the NPCs one by one. For each NPC, you have the choice to go to it or not. Say dp[K][0] is the answer given K hours and not going to the NPC and dp[K][1] is the answer given K hours and going to the NPC. Then dp[K][1] is the maximum of dp[K-h_i][0]+g_i and dp[K-t_i][1]+q_i. So the answer can be computed using this.

Time complexity: \mathcal{O}(NH)


Comments

There are no comments at the moment.