[02156]ワインの試飲

[02156]ワインの試飲

質問する

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

しゅつりょく

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

コード#コード#

#include <iostream>
#include <cstring> // memset

using namespace std;

/* 조건 */
#define MAX_N 10001

/* 변수 */
int N;
int wine[MAX_N], memo[MAX_N];

/* 함수 */
int max3(int a, int b, int c) {
    return max(a, max(b, c));
}

int dp(int idx) {
    if(idx < 0) return 0;
    int& ret = memo[idx];
    if(ret > -1) return ret;
    return ret = max3(dp(idx-1), wine[idx] + dp(idx-2), wine[idx] + wine[idx-1] + dp(idx-3));
}

int main() {
    /* 입력 */
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> wine[i];
    }

    /* 풀이 */
    memset(memo, -1, sizeof(memo));

    /* 출력 */
    cout << dp(N-1) << '\n';
}

解法

ろんり

この問題は[02578]階段を登る題とあまり違わない.
しかし、この問題にスキップできる回数の制限がないことを考慮して、最低価格を求めるべきです.
N番目のグラスに対して取れる行動(?)3種類あります.
1.Nをスキップします.
2.Nを飲んでN+1をスキップします.
3.NとN+1を飲んでN+2をスキップします.
以上の3つの状況が何であれ,無限反復は条件に合致するすべての状況となる.
したがって,以上を繰り返してNを返す値が正解となる.

n.関数

max3(a, b, c)
この関数はa,b,cの3つの数の中で最も価値のある関数を探し出す.

dp(idx)
この関数は,解法を担当する関数である.

idx<0は範囲外を示す、最大値

に影響を及ぼさないように0を返す.

時間の制限があるため、コメントにコメント[]配列を作成し、計算された値をコメントに格納します.
memo[]配列に値がある場合は、再帰関数ではなく値を返します.
memo[]配列はdp()関数を返すときにmemoに格納される.

の上の3つのケースは以下のように示され、その中の最値を返しmemo[]配列に格納される.

dp(idx-1)

wine[idx] + dp(idx-2)

wine[idx] + wine[idx-1] + dp(idx-3))

main()

Nと入力します.

Nのようにワイン[]配列入力を受けます.

注記[]の配列を-1にリセットします.

dp(N−1)(入力は0から、従ってN−1から)関数を実行し、結果を出力する.

ソース

白ワインを味わう
https://www.acmicpc.net/problem/2156