ABC369 D問題〜DP〜

解説動画

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

コード

#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 a(n);
    rep(i, n) cin >> a[i];

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

    for (int i = 1; i < n; i++) {
        dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + 2 * a[i]);
        dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + a[i]);
    }

    // dpの確認のためのcout
    // for (auto vec : dp) {
    //     for (auto e : vec) {
    //         cout << e << " ";
    //     }
    //     cout << endl;
    // }

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