ワインを味わう

白駿2156

最も大量のワインを手に入れた.

孝珠はワイン試飲会に行きました.そこへ行くと、テーブルの上にいろいろなワインが盛られたグラスが並んでいました.孝珠はワインを味わいます.ここには2つのルールがあります.

ブドウグラスを選択した場合、このカップのワインはすべて飲んで、飲んだ後に元の場所に戻すべきです.

が並んでいる3杯を全部飲み干すわけにはいかない.

孝珠はワインをできるだけ多く味わうために、どんなワイングラスを選ぶべきか悩んでいます.

1からnの番号のn個のブドウの杯を順番にテーブルの上に置いて、各ワインの杯の中のブドウの酒の量が与えられる時、プログラムを編纂して、あなたが最も多くのワインを飲むのを助けてください.

行目はブドウグラスの個数nを与える.(1≦n≦10000)第2列からn+1列まで、ワインカップ中のブドウ酒の量が順次与えられる.

ワインの量は1000以下の音ではなく整数です.

にゅうしゅつりょく

入出力66101398133

方法

:dpで解く.階段を登るように、ワインを3つ連続で飲むことはできません.

今ワイン+直接前酒+前酒を飲むdp

今ワイン+前のdpを飲んで
この2つの比較は最大値を保存します.
しかし、エラーが発生しました.
最後の一杯は飲まないかもしれないので、出力はdp[-1]ではなくmax(dp)ですが、やはり間違っています.

知るところ

今でもワインを飲まないことを考えるべきです.
階段を登る問題では、一度に1段か2段まで登ることができますが、ワインにはそんな条件はないので、必ずしも飲む必要はありません.
ex.[10400,5,6,7100]で100+400+7+100を飲むのが一番価値があります.

コード#コード#

n = int(input())
wine = []
for _ in range(n):
    wine.append(int(input()))

dp = []
dp.append(wine[0])
if n == 1:
    print(dp[0])
    exit()
dp.append(wine[0]+wine[1])
if n==2:
    print(dp[1])
    exit()

dp.append(max(dp[1], wine[0]+wine[2], wine[1]+wine[2]))
for i in range(3, n):
    dp.append(max(dp[i-1], wine[i]+wine[i-1]+dp[i-3], wine[i]+dp[i-2]))

print(max(dp))