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)$ ~\mathcal{O}(2^NNH)~

For subtask 2, the problem is exactly unbounded knapsack.

Time complexity: $\mathcal{O}(NH)$ ~\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]$ ~dp[K][0]~ is the answer given $K$ ~K~ hours and not going to the NPC and $dp[K][1]$ ~dp[K][1]~ is the answer given $K$ ~K~ hours and going to the NPC. Then $dp[K][1]$ ~dp[K][1]~ is the maximum of $dp[K-h_i][0]+g_i$ ~dp[K-h_i][0]+g_i~ and $dp[K-t_i][1]+q_i$ ~dp[K-t_i][1]+q_i~. So the answer can be computed using this.

Time complexity: $\mathcal{O}(NH)$ ~\mathcal{O}(NH)~

Comments

There are no comments at the moment.