Editorial for DMOPC '19 Contest 4 P3 - Taking Cues

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.

Authors: richardzhang, Riolku

We can apply dynamic programming to this problem. Note that for each state it suffices to track the month and the number of cue balls. Since Veshy can have at most $100$ ~100~ cue balls, this is only $100N$ ~100N~ states, which is fine.

For each state, we consider selling some or all of his cue balls. Let $dp[m][i]$ ~dp[m][i]~ be the maximum money we can have after $m$ ~m~ months when we own $i$ ~i~ cue balls. Then:

$\displaystyle dp[m][i] = \max_{0 \le j \le \min(100-i, Y_i)} dp[m-1][i+j] + j \times s_i$

Also, after we consider selling cue balls, we can consider buying some cue balls.

$\displaystyle dp[m][i] = \max_{0 \le j \le \min(i, X_i)} dp[m-1][i-j] - j \times b_i$

Finally, make sure to subtract the maintenance costs from each state. (So $dp[m][i] := dp[m][i] - M \times i$ ~dp[m][i] := dp[m][i] - M \times i~ for $1 \le i \le 100$ ~1 \le i \le 100~)

Time Complexity: $\mathcal O(NK^2)$ ~\mathcal O(NK^2)~, where $K$ ~K~ is the number of cue balls we can hold at once. In this case, it is $100$ ~100~.

Comments

0

max commented on Jan. 19, 2020, 11:54 a.m. ← edit 2 →

What were the intended solutions for Subtasks 1 and 2?

Edit: Additionally, how would this problem be solved if it was possible to sell cue balls purchased in the same month that they were bought?