白俊-ワインを味わう(2156)

Dynamic Programming

質問する

孝珠はワインの試飲会に行きました.そこへ行くと、テーブルの上にいろいろなワインが盛られたグラスが並んでいました.孝珠はワインを味わいます.ここには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以下の音ではなく整数です.

しゅつりょく

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

import sys

n = int(sys.stdin.readline())

arr = [0] * (n + 3)
for i in range(3, n + 3):
    arr[i] = int(sys.stdin.readline())
    
table = [0 for i in range(len(arr))] 

for i in range(3, n + 3):
    table[i] = max(table[i - 1], table[i - 2] + arr[i], table[i - 3] + arr[i - 1] + arr[i])
    #max안에는 순서대로 
    # i - 1까지의 최댓값 & i 안마시기 
    # i - 2까지의 최댓값 & i - 1 안마시기 & i 마시기
    # i - 3까지의 최댓값 & i - 1 마시기 & i 마시기
    # table의 각 원소는 해당 인덱스까지 와인을 마셨을 때 최댓값 넣기
print(table[len(table) - 1])

maxを求めるときに増加する値がtableになり、arrの基準は飲むものをarrで処理し、飲まないものの前の計算は最値を考慮するのでtable値を増加します.
参照)
https://in0-pro.tistory.com/26
https://pacific-ocean.tistory.com/152