【1つずつ丁寧に！】ABC306 D問題〜DP〜

ABC

解説動画

動画内の説明で利用していたファイル


dp[料理i][状態j] := "料理i"までを食べるか見送るかを選択した時の"状態j"である時のポイントの合計の最大値

dpテーブル (n + 1)行2列
    dp[0][0] = 0 とする
    ("-1"は,ありえない状態を意味する)
        dp[0][1] = -100

1つ上のものと自分を比較して大きい方に更新する.
    dp[i + 1][0] = max(dp[i + 1][0], dp[i][0]);
    dp[i + 1][1] = max(dp[i + 1][1], dp[i][1]);

解毒剤入り
x[i] == 0
    dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + y[i])
        ("元々の点数"と"1つ前の毒状態から料理iを食べた後の点数"の大きい方)
    dp[i + 1][0] = max(dp[i + 1][0], dp[i][0])
        ("元々の点数"と"1つ前の元気な状態から食べなかった後の点数"の大きい方)
毒あり
x[i] == 1
    dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + y[i])
        ("元々の点数"と"1つ前の元気な状態から料理iを食べた後の点数"の大きい方)

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    vector x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    vector<vector> dp(n + 1, vector(2, -1));
    dp[0][0] = 0;

    rep(i, n) {
        dp[i + 1][0] = max(dp[i + 1][0], dp[i][0]);
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][1]);

        if (x[i] == 0) {
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + y[i]);
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + y[i]);
        } else {
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + y[i]);

        }
    }

    // cout << "====" << endl;
    // for (auto row : dp) {
    //     for (auto e : row) {
    //         cout << e << " ";
    //     }
    //     cout << endl;
    // }

    cout << max(dp[n][0], dp[n][1]) << endl;

    return 0;
}

コメント