すべての動物に \(1\) 回以上餌をあげるには、明らかに、同じ種類の行動を \(2\) 回以上行う必要はありません。 よって、\(N\) 種類の行動（行動 \(1\) 、行動 \(2\) 、\(\ldots\)、行動 \(N\) と呼ぶ）それぞれについて、それを \(1\) 回行うか行わないかを決定すれば良いです。

すべての動物に \(1\) 回以上餌をあげるには、

• 動物 \(1\) に餌をあげる必要があるので、行動 \(N\) と行動 \(1\) のうち少なくとも一方を行わなければなりません。
• 動物 \(2\) に餌をあげる必要があるので、行動 \(1\) と行動 \(2\) のうち少なくとも一方を行わなければなりません。
• 動物 \(3\) に餌をあげる必要があるので、行動 \(2\) と行動 \(3\) のうち少なくとも一方を行わなければなりません。
• \(\cdots\)
• 動物 \(N\) に餌をあげる必要があるので、行動 \((N-1)\) と行動 \(N\) のうち少なくとも一方を行わなければなりません。

本問題は、「上記の \(N\) 個の条件をすべて満たすように\(N\) 種類の行動それぞれについて行うか行わないかを決定する」ときの、合計費用を最小化する問題です。

これを動的計画法（DP）によって解きます。 \(i = 1, 2, \ldots, N\) の順番で「 \(A_i \)円払って行動 \(i\) を行う」か「行動 \(i\) を行わない」かを、上述の\(N\)個の条件に違反しないように決定していくことを考えます。 DPテーブルとして、\(i = 0, 1, \ldots, N\) と \(j = 0, 1\) について \(\mathrm{dp}[i][j]\) を

\(\mathrm{dp}[i][j] := \) （行動 \(1, 2, \ldots, i\) までは行うかどうかを決定しており、さらに、行動 \(i\) は \(j\) 回行うときの、それまでにかかる合計費用としてあり得る最小値）

とおきます。

「行動 \(1\) を行う場合」と「行動 \(1\) を行わない場合」の \(2\) 通りに場合分けし、それぞれの場合でDPテーブル \(\mathrm{dp}[\ast][\ast]\) を埋めていくことで答えを計算します。 その後、「行動 \(1\) を行う場合」の答えと「行動 \(1\) を行わない場合」の答えのうち小さい方を選べば本問題の答えが得られます。

[1] 行動 \(1\) を行わない場合

まず、 DPの初期化を考えます。 DPテーブルの定義から、\(\mathrm{dp}[1][0] = 0\) です。 また、行動 \(1\) を行うことは考えないので、便宜上 \(\mathrm{dp}[1][1] = \infty\) としておきます。

次に、DPの遷移を考えます。 すなわち、\(\mathrm{dp}[1][\ast], \mathrm{dp}[2][\ast], \ldots \mathrm{dp}[i-1][\ast]\) までの値がわかっているとき、\(\mathrm{dp}[i][0]\) と \(\mathrm{dp}[i][1]\) の値を求めます。 まず、行動 \(i\) を行わないことが許されるのは、行動 \((i-1)\) を行ったときのみなので、

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

です。 一方で、行動 \(i\) を行う場合は、行動 \((i-1)\) を行っていてもいなくても良いです。また、行動 \(i\) を行うことで \(A_i\) 円の費用がかかります。よって、

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

です。

上記の初期化と漸化式 (1), (2) によって 「 \(i = 1, 2, \ldots, N\) のすべてについて \(\mathrm{dp}[i][0]\) と \(\mathrm{dp}[i][1]\) を求める」ことを \(\mathrm{O}(N)\) 時間でできます。

動物 \(1\) に餌をあげる必要があることに関して、いま行動 \(1\) を行わない場合を考えているので、行動 \(N\) は必ず行わなければなりません。 よって、\(\mathrm{dp}[N][0]\) と \(\mathrm{dp}[N][1]\) のうち \(\mathrm{dp}[N][1]\) が「行動 \(1\) を行わない場合」の答えとなります。

[2] 行動 \(1\) を行う場合

まず、 DPの初期化を考えます。 行動 \(1\) を行うのに \(A_1\) 円の費用がかかるので、DPテーブルの定義より、\(\mathrm{dp}[1][1] = A_1\) です。 また、行動 \(1\) を行わないことは考えないので、便宜上 \(\mathrm{dp}[1][0] = \infty\) としておきます。

DPの遷移には「行動 \(1\) を行わない場合」と同様に漸化式 (1), (2) を用いることができます。 これによって「 \(i = 1, 2, \ldots, N\) のすべてについて \(\mathrm{dp}[i][0]\) と \(\mathrm{dp}[i][1]\) を求める」ことを \(\mathrm{O}(N)\) 時間でできます。

動物 \(1\) に餌をあげる必要があることに関して、いまは行動 \(1\) を行う場合を考えているので、行動 \(N\) は行っても行わなくても良いです。 よって、\(\mathrm{dp}[N][0]\) と \(\mathrm{dp}[N][1]\) のうち小さい方が「行動 \(1\) を行う場合」の答えとなります。

以上より、本問題を \(\mathrm{O}(N)\) 時間で解くことができます。

以下に C++ 言語による正解例を記載します。

#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;
}