E - Work or Rest Editorial by SamDaBest
Solution with Knapsack DPObserve that the productivity of the weekdays between two holiday is fixed.
Therefore, we can calculate the productivity \(P_i\) for each holidays on day \(a\) and \(b\) where \(i = |a-b|\) .We have \(P_{i+1}= a_1 + \cdots + a_{\lceil \frac{i}{2} \rceil}+ \cdots + a_1\) for odd \(i\) and \(P_{i+1} = a_1 + \cdots + a_{\lfloor \frac{i}{2} \rfloor} + a_{\lfloor \frac{i}{2} \rfloor} + \cdots + a_1\) for even \(i\).
This can be precalculated using loops or prefix sums in \(\mathcal{O}(n)\).
After calculating the productivity, the problem can be transformed into a infinite knapsack dp, where there are \(n\) items, and each item have an pair (weight, value) equals to \((i, P_i)\).
Let \(dp[i]\) be the maximum value such that the total weight is \(i\). As the sum of difference of the holidays is \(n\), the answer would be \( dp[n]\).
Let’s consider the first sample.
The productivity for each gap for the sample would be \(P_1 = 0, P_2= 10, P_3 = 20, P_4= 30, P_5= 40, P_6= 41, P_7= 42,\).
Then the maximum productivity would be \(P_2 + P_5= 50\).
Thus, the problem is solved in \(\mathcal O(n^2)\).
posted:
last update: