In order to feed every animal at least once, obviously, he does not have to perform the same action twice or more. Therefore, it is sufficient to determine for each of \(N\) kinds of actions (which we call Action \(1\), Action \(2\), \(\ldots\), and Action \(N\)) if he should perform it once or zero times.

In order to feed every animal at least once,

• he needs to feed Animal \(1\), so at least one of Action \(N\) and Action \(1\) should be performed;
• he needs to feed Animal \(2\), so at least one of Action \(1\) and Action \(2\) should be performed;
• he needs to feed Animal \(3\), so at least one of Action \(2\) and Action \(3\) should be performed;
• \(\cdots\)
• he needs to feed Animal \(N\), so at least one of Action \((N-1)\) and Action \(N\) should be performed.

This problem asks to minimize the total cost when “determining for each of \(N\) kinds of actions if it should be done so that all of the \(N\) conditions above are satisfied.”

We solve it with Dynamic Programming (DP). For each \(i = 1, 2, \ldots, N\) in this order, let us determine which we should choose: “paying \(A_i\) yen to perform Action \(i\)” or “not performing Action \(i\).” Here, we must not violate the \(N\) conditions above. Let us define the DP table \(\mathrm{dp}[i][j]\) for \(i = 0, 1, \ldots, N\) and \(j = 0, 1\) by:

\(\mathrm{dp}[i][j] := \) (minimum possible total cost spent so far when we have already determined if he should perform Action \(1, 2, \ldots, i\) and when Action \(i\) is performed \(j\) times).

We divide into two cases: “when Action \(1\) is performed” and “when Action \(1\) is not performed,” and fill the DP table \(\mathrm{dp}[\ast][\ast]\) in each case. Afterwards, the answer can be obtained as the smaller of the answer for “Action \(1\) being performed” and that for “Action \(1\) not being performed.”

[1] When Action \(1\) is not performed

First, we consider the initialization of the DP. By the definition of DP, \(\mathrm{dp}[1][0] = 0\). Also, since we do not consider doing Action \(1\), we let \(\mathrm{dp}[1][1] = \infty\) for convenience.

Next, we consider the transition of the DP. That is, when we already know the values of \(\mathrm{dp}[1][\ast], \mathrm{dp}[2][\ast], \ldots \mathrm{dp}[i-1][\ast]\), we are going to determine the values of \(\mathrm{dp}[i][1]\). First, Action \(i\) is allowed to be skipped only when Action \((i-1)\) has been done, so

\[\mathrm{dp}[i][0] = \mathrm{dp}[i-1][1] \tag{1}.\]

On the other hand, if Action \(i\) is performed, Action \((i-1)\) does not necessarily have to be done. Also, doing Action \(i\) costs \(A_i\) yen. Therefore,

\[\mathrm{dp}[i][1] = \min\lbrace \mathrm{dp}[i-1][0], \mathrm{dp}[i-1][1]\rbrace + A_i \tag{2}.\]

By the initialization above and the recurrence relations (1) and (2), we can “find \(\mathrm{dp}[i][0]\) and \(\mathrm{dp}[i][1]\) for every \(i = 1, 2, \ldots, N\)” in a total of \(\mathrm{O}(N)\) time.

Regarding feeding Animal \(1\), since we assume the case that Action \(1\) is not performed, Action \(N\) must be performed. Therefore, only \(\mathrm{dp}[N][1]\), but not \(\mathrm{dp}[N][0]\), is the answer for the case “when Action \(1\) is not performed.”

[2] When Action \(1\) is performed

First, we consider the initialization of the DP. Since it costs \(A_i\) yen to perform Action \(1\), by the definition of the DP table, \(\mathrm{dp}[1][1] = A_1\). Also, since we do not consider not doing Action \(1\), we let \(\mathrm{dp}[1][0] = \infty\) for convenience.

As the transitions of DP, we can use the recurrence relations (1) and (2) just as in “when Action \(1\) is not performed.” This enables us to “find \(\mathrm{dp}[i][0]\) and \(\mathrm{dp}[i][1]\)” in a total of \(\mathrm{O}(N)\) time.

Regarding feeding Animal \(1\), since we assume the case that Action \(1\) is performed, Action \(N\) may not be performed. Therefore, the smaller of \(\mathrm{dp}[N][0]\) and \(\mathrm{dp}[N][1]\) is the answer for the case when “Action \(1\) is performed.”

Therefore, this problem can be solved in about \(O(N)\) time.

The following is a sample accepted code in C++ language.

#include <iostream>
using namespace std;
typedef long long ll;
const ll inf = 1e18;

int n;
int a[300005];
ll dp[300005][2];

int main(void)
{
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  
  ll ans = inf;
  for(int t = 0; t <= 1; t++){
    dp[1][t] = a[1]*t, dp[1][1-t] = inf;
    
    for(int i = 2; i <= n; i++){
      dp[i][0] = dp[i-1][1];
      dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + a[i];
    }
    if(t == 0) ans = min(ans, dp[n][1]);
    if(t == 1) ans = min(ans, min(dp[n][0], dp[n][1]));
  }
  cout << ans << endl;
  
  return 0;
}