白準2156号-ワイン試食(★//▽/1):Python

概要

回答時間:30～40分

時間制限:2秒

メモリ制限:128 MB

機出:backjoon

リンク:https://www.acmicpc.net/problem/21562

質問する

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

しゅつりょく

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

解決策

問題を理解する

この問題もダイナミックプログラミングの問題です.最近ずっとDynamicで遊んでいます...次は別のタイプを解く(解かないとまた忘れてしまう)
いずれにしても、ルールを探すのに少し時間がかかった以外は、簡単に実現できます.でも….思いがけない場所で捕まえられた...

アルゴリズム#アルゴリズム#

ルールはこうです.0残忍の場合、1残忍の場合、2残忍の場合、3行を区別するために、それぞれ計算すればよい.

0残忍:この順番でワインを飲まない

1残忍な状況:前回は酒を飲まず、次回は酒を飲まない

残忍な状況:前回はワインを飲んだが、今回はワインを飲んだ.
正直、これでいいと思った.しかし、反例がある以上.

6
8 2 0 0 2 8

本来なら20が正解だったはずなのに、間違ったところが出てきたので20ではなく18が出てきました.したがって、新しいルールは次のとおりです.これにより、常に最大値を維持できます.

dp[0][i] = max(dp[1][i - 1], dp[2][i - 1])
dp[1][i] = max(juice[i] + dp[0][i - 1], dp[0][i])
dp[2][i] = max(juice[i] + dp[1][i - 1], dp[0][i])

Python

マイコード

import copy
import sys

input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    juice = []
    for _ in range(n):
        juice.append(int(input()))
    dp = [[0 for _ in range(n)] for _ in range(3)]

    if n == 1:
        print(juice[0])
    else:
        dp[1][0] = juice[0]
        for i in range(1, n):
            dp[0][i] = max(dp[1][i - 1], dp[2][i - 1])
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + juice[i])
            dp[2][i] = juice[i] + dp[1][i - 1]

            print(dp)
        print(max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]))

残念なことに、反例はよく考えられなかった.問題を入力すればいいと思ったのですが...あら.この問題の正解率が30%くらいだったのもそのせいだと思います.