[C++]2156ワインを味わう

👉 味道葡萄酒

[正解コード]

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n, i;
    int podo[10000] = {0};
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> podo[i]; 
    }
    int memo[10000][3] = {{0, 0, 0}};
    memo[0][1] = podo[0];
    for (i = 1; i < n; i++) {
        memo[i][0] = *max_element(memo[i - 1], memo[i - 1] + 3);
        memo[i][1] = memo[i - 1][0] + podo[i];
        memo[i][2] = memo[i - 1][1] + podo[i];
    }
    cout << *max_element(memo[n - 1], memo[n - 1] + 3) << endl;
    return 0;
}

[回答]

問題の条件(ワインを3杯連続で飲めない)により、3*10000の順で記録しました.

の第1列は、第n種のワインを飲まない最高価格を示している.つまり、前項の値に最値を入れればよい.*max_element(memo[i - 1], memo[i - 1] + 3)

の2列目はn杯目のワインを飲むことを意味し、この杯は1杯連続の時である.memo[i - 1][0] + podo[i]

の3列目はn杯目のワインを飲むことを意味し、この1杯は2杯連続の時である.memo[i - 1][1] + podo[i]

✔ max_elemnt()

<>

区間(array、list、vectorなど)で最値を求めます.

は、対応する値のアドレス

を返す.

は、全てのSTL容器において線形動作を行う.時間複雑度=O(N)

参照と例

[アプリケーション構造とアルゴリズム]

Dynamic Programming