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.

last update: