【ABC140 C】「Maximal Value」を解く【Python3】

長さN-1の整数列Bが与えられたとき、条件に沿うような、整数列Aの総和として考えられる最大値を求める問題です。

特定のA_iの取りうる最大値は、Bの隣り合う要素の小さい方と同じであると考えると解くことができます。

提出

n = int(input())
b = list(map(int, input().split()))
a = []

for i in range(n-2):
    a.append(min(b[i],b[i+1]))

print(sum(a)+b[0]+b[n-2])

例えば、A₂の最大値は「B₁とB₂の最小値」となります。

A₁とA_Nのみがこの条件と異なるので、これだけ最後に計算します。

プログラムで書くときは、インデックスが0始まりであることに注意して、「A₂〜A_N-1」のリストを作成します。

このリストの合計と、B₁とB_N-1を足し合わせたものが答えになります。

（A₁の最大値はB₁、A_Nの最大値はB_N-1と考えることができます）

【ABC140】解説記事リスト