ABC140 C - Maximal Value

問題はこちら atcoder.jp

方針

のように を小さくしながら考えます。それぞれの に対して を最大にする貪欲法を用いています。ある A_i は B_i-1, B_i にのみ制約されるので，貪欲法で最適解が求まります。

（アルゴリズムがほぼ分からないので雰囲気で言ってます。間違い等あればご指摘ください。）

コード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;

    vector<int> a(n),b(n-1);
    for(int i=0; i<n-1; i++){
        cin>>b[i];
    }

    int sum=0;
    a[n-1]=b[n-2];

    for(int i=n-2; i>0; i--){
        if(b[i-1]>b[i]){
            a[i]=b[i];
        }else{
            a[i]=b[i-1];
        }
    }

    a[0]=b[0];

    for(int i=0; i<n; i++){
        sum+=a[i];
    }

    cout<<sum<<endl;
}