Contest Duration: - (local time) (100 minutes) Back to Home

## E - Takahashi and Animals Editorial by spheniscine

If we change the statement such that the $$N$$-th action does not feed animal $$1$$, we can solve it with DP. $$dp_i$$ is the miminum cost needed to feed the first $$i$$ animals, and $$dp_i = \min (dp_{i-1} + A_i, dp_{i-2} + A_{i-1})$$.

To account for the original stipulation that the $$N$$-th action feeds animal $$1$$, we should run this DP twice, once on the full array, and once on the array without the first and the last element, adding $$A_N$$ to the latter answer. Pick the minimum of the two. (i.e. if the answer of the above DP on an array $$A$$ is denoted by $$f(A_1, ..., A_N)$$, the answer is $$\min (f(A_1, ..., A_N), f(A_2, ..., A_{N-1}) + A_N))$$ ). This is because if the $$N$$-th action is not taken in the optimal choice, the first value will be the answer, otherwise, the second value will be the answer.

posted:
last update: