Editorial for TLE '16 Contest 6 (Mock CCC) J5 - Meal Plan

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.

We can make a 2-dimensional integer array $dp[N+1][3]$ ~dp[N+1][3]~. For any $H$ ~H~ $(0 \le H < N)$ ~(0 \le H < N)~ and $X$ ~X~ $(0 \le X \le 2)$ ~(0 \le X \le 2)~, $dp[H][X]$ ~dp[H][X]~ represents how many different ways the student can spend $H$ ~H~ dollars and have the last meal as $X$ ~X~ ( $X = 0$ ~X = 0~ means breakfast, $X = 1$ ~X = 1~ means lunch, and $X = 2$ ~X = 2~ means dinner).

To start off, we know that the first meal must be breakfast, so we scroll through the breakfast options and add $1$ ~1~ to every $dp[b_i][0]$ ~dp[b_i][0]~.

Scrolling through the array, as we get to $dp[H][0]$ ~dp[H][0]~, we do $3$ ~3~ steps, one for every meal of the day.

For each lunch option, we add $dp[H][0]$ ~dp[H][0]~ to $dp[H+l_i][1]$ ~dp[H+l_i][1]~, since the student's next meal after breakfast must be lunch;
Similarly, as we get to $dp[H][1]$ ~dp[H][1]~, then for each dinner option, we add $dp[H][1]$ ~dp[H][1]~ to $dp[H+d_i][2]$ ~dp[H+d_i][2]~, since the student's next meal after breakfast must be dinner;
Lastly, as we get to $dp[H][2]$ ~dp[H][2]~, then for each breakfast option, we add $dp[H][2]$ ~dp[H][2]~ to $dp[H+b_i][0]$ ~dp[H+b_i][0]~, since after breakfast, the student can then begin considering the next day's breakfast.

In the end, we can find the number of ways to pay the most by taking the highest value of $h$ ~h~ where $dp[h][0]+dp[h][1]+dp[h][2] > 0$ ~dp[h][0]+dp[h][1]+dp[h][2] > 0~.

Time Complexity: $\mathcal{O}(N \times (B+L+D))$ ~\mathcal{O}(N \times (B+L+D))~

Comments

There are no comments at the moment.