解説

ABC140のC問題の解説です。貪欲法（？）問題です。

数列 $A_i$ をリストAsに、数列 $B_i$ をリストBsに置き換えて考えます。AsとBsは0-originです。

Bs[i] >= max(As[i], As[i+1]) の条件を満たすようにAs[i+1] の値を貪欲的に埋めていく問題です。

最初に初期値のAs[0]とAs[1]を決めます。これはBs[0]とBs[1]の大きさを比較すれば一意に定まります。

たとえば、Bs[0]=10, Bs[1]=20のとき、Bs[i] >= max(As[i], As[i+1]) より、As[0] =10, As[1] = 10 と求まります。

    # 初期値を決める
    As = [0] * N
    if Bs[0] <= Bs[1]:
        # As:  ?   ?   →   As: 10  10
        # Bs: 10  20   →   Bs: 10  20
        As[0] = As[1] = Bs[0]
    else:
        # As:  ?   ?   →   As: 20  10
        # Bs: 20  10   →   Bs: 20  10
        As[0], As[1] = Bs[0], Bs[1]

あとは Bs[i] >= max(As[i], As[i+1]) の条件を満たすようにAs[i+1] の値を貪欲的に埋めていけばOKです。

数列の最後のAs[N-1] だけ例外で、これは必ずBs[N-2]になります。

    # 貪欲法
    for i in range(1, N-2):
        if Bs[i] > Bs[i+1]:
            # As:   ■    ?  →  As:   ■    0
            # Bs: 153    0  →  Bs: 153    0
            As[i+1] = Bs[i+1]
        else:
            # As:   ■    ?  →  As:   ■  153
            # Bs: 153  160  →  Bs: 153  160
            As[i+1] = Bs[i]
    As[N-1] = Bs[N-2]

コーナーケース

N == 2 の場合、答えは必ず Bs[0]*2 になる

実装

# -*- coding:utf-8 -*-
import sys

"""
Bs[i] >= max(As[i], As[i+1]) を満たす条件で、

sum(As)の最大値を求める問題
"""

def solve():
    N = int(sys.stdin.readline())
    Bs = list(map(int, sys.stdin.readline().split()))

    if N == 2:
        print(Bs[0]*2)
        return

    # 初期値を決める
    As = [0] * N
    if Bs[0] <= Bs[1]:
        # As:  ?   ?   →   As: 10  10
        # Bs: 10  20   →   Bs: 10  20
        As[0] = As[1] = Bs[0]
    else:
        # As:  ?   ?   →   As: 20  10
        # Bs: 20  10   →   Bs: 20  10
        As[0], As[1] = Bs[0], Bs[1]

    # 貪欲法
    for i in range(1, N-2):
        if Bs[i] > Bs[i+1]:
            # As:   ■    ?  →  As:   ■    0
            # Bs: 153    0  →  Bs: 153    0
            As[i+1] = Bs[i+1]
        else:
            # As:   ■    ?  →  As:   ■  153
            # Bs: 153  160  →  Bs: 153  160
            As[i+1] = Bs[i]
    As[N-1] = Bs[N-2]

    print(sum(As))


if __name__ == "__main__":
    solve()