Editorial for DMOPC '17 Contest 1 P4 - Quests - Olympiads Online Judge

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)$ $O (2^{N} N H)$

For subtask 2, the problem is exactly unbounded knapsack.

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

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]$ $d p [K] [0]$ is the answer given $K$ $K$ hours and not going to the NPC and $dp[K][1]$ $d p [K] [1]$ is the answer given $K$ $K$ hours and going to the NPC. Then $dp[K][1]$ $d p [K] [1]$ is the maximum of $dp[K-h_i][0]+g_i$ $d p [K - h_{i}] [0] + g_{i}$ and $dp[K-t_i][1]+q_i$ $d p [K - t_{i}] [1] + q_{i}$ . So the answer can be computed using this.

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

Comments

There are no comments at the moment.