[AtCoder] ABC 140 C – Maximal Value

2019年9月8日

問題

方針

条件を具体的に書き出すと、

\[\begin{eqnarray}
\max(A_1, A_2) &\leq& B_1\\
\max(A_2, A_3) &\leq& B_2\\
&\vdots&\\
\max(A_{N-2}, A_{N-1}) &\leq& B_{N-2}\\
\max(A_{N-1}, A_N) &\leq& B_{N-1}\\
\end{eqnarray}
\]

となり、\( A_1 \) と \( A_N \) は不等式の制約が一つであることが分かります。よって、\( A_1 = B_1 \), \( A_N = B_{N-1}\) のとき総和を最大化します。その他のものについて考えると、\( A_2 \) については、

\[
A_2 \leq B_1 \wedge \max(A_2, A_3) \leq B_2
\]

なので、\( A_2 = \min(B_1, B_2) \) となります。同様に考えて、\( A_i = \min(B_{i-1}, B_{i}) \ (2 \leq i \leq N – 1)\) となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N;
  cin >> N;
  ll B[N - 1];
  for (int i = 0; i < N - 1; i++) {
    cin >> B[i];
  }
  ll sum = B[0] + B[N - 2];
  for (int i = 0; i < N - 2; i++) {
    sum += min(B[i], B[i + 1]);
  }
  cout << sum << "\n";
  return 0;
}