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

abc140c

コンテスト一覧へ

 

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

特定のAiの取りうる最大値は、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])

例えば、A2の最大値は「B1とB2の最小値」となります。

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

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

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

(A1の最大値はB1、ANの最大値はBN-1と考えることができます)

【ABC140】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。