AtCoder ABC 140 C - Maximal Value (灰色, 300 点)

数学嫌いの方は問題文読んだ瞬間に一瞬敬遠心が生まれてしまうかもしれない...でも落ち着けば難しくはない

問題へのリンク

問題概要

長さ の数列 (具体的な値はわからない) に対して

• 

を満たす数列 が与えられます。 の総和として考えられる最大値を求めてください。

制約

• 

考えたこと: まずは手で様子をつかむ

こういう一見してよくわからないな...と感じた問題は、あれこれ手で実験してみるに限る。

たとえば とかだったら、

• 
• 
• 
• 
• 
• 

でなければならないことがわかる。よってこれを満たす範囲で をできるだけ大きくしようと思うと となる。

一般化

この時点で、 の各要素は両端を除くと「 の隣り合う要素の最小値以下である」ということがわかる。上の例だと、 は のうちの と の最小値以下であったし、 は と の最小値以下であった。

同様に の両端も、 の両端の値以下であることがわかる。

そして、 の両端の値を の両端の値そのものにして、 の両端以外の値も の隣り合う二要素の最小値そのものにしても、条件を満たしているので、それが最適解である。

まとめると

• 
• 
• 
• ...
• 
• 

とすれば OK。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> B(N-1);
    for (int i = 0; i < N-1; ++i) cin >> B[i];

    long long res = B[0] + B.back();
    for (int i = 0; i + 1 < B.size(); ++i) {
        res += min(B[i], B[i+1]);
    }
    cout << res << endl;
}