[python]白駿/ワイン試飲/215号/DP

DPコンセプトショートカット
質問する
ワイン試飲問題リンク
孝珠はワインの試飲会に行きました.そこへ行くと、テーブルの上にいろいろなワインが盛られたグラスが並んでいました.孝珠はワインを味わいます.ここには2つのルールがあります.

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

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

できるだけ多くのワインを味わうために、孝珠はどのワイングラスを選ぶべきか悩んでいる.1からn番のn個のブドウの杯は順番にテーブルの上に置いて、各ブドウの杯の中のブドウの酒の量はタイミングをあげて、1つのプログラムを編纂して、あなたが最も多くのワインを飲むことを助けてください.
例えば、6個のブドウグラスがあり、各コップの中に6、10、13、9、8、1の順であれば、1番目、2番目、4番目、5番目のブドウグラスを選択すれば、総ブドウ酒量は最大33に達することができる.
入力
最初の行はブドウのコップの個数nを与えます.(1≦n≦10000)第2列からn+1列まで、ワインカップ中のブドウ酒の量が順次与えられる.ワインの量は1000以下の音ではなく整数です.

6
6
10
13
9
8
1

しゅつりょく
最初の行で飲める最大のブドウ酒の量を出力します.

33

方法
dp値に今までワインを飲んだ最大量を貯蔵する
現在位置iの場合
i-3までのdp値+i-1のブドウ酒量+iのブドウ酒量=1番
i-2までのdp値+iのブドウ酒量=2号
i-1までのdp値=3回
1,2,3回の最大値は現在のdp[i]に格納される
? : オレンジ部分の和の中で最安値
コード#コード#

# url : https://www.acmicpc.net/problem/2156
# 난이도 : silver 1

import sys

n = int(input())

dp = [0] * 10001

wine_list = [0] + [int(sys.stdin.readline()) for _ in range(n)]

dp[1] = wine_list[1]

if n >= 2 :
    dp[2] = wine_list[1] + wine_list[2]

for i in range(3,n+1):
    dp[i] = max(dp[i-3] + wine_list[i-1] + wine_list[i], dp[i-2] + wine_list[i], dp[i-1])

print(dp[n])