Yukicoder045 回転寿司

問題概要

あなたは、回転寿司にきている。
お寿司は$N$皿が順番に流れてくる。$N$皿のお寿司のそれぞれの美味しさが$V[i]$で表される。

流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、 連続で皿を取ることが出来ない。 もちろん、自分の前を過ぎたお寿司も取ることが出来ない。

この時、あなたが得られる美味しさの最大の合計値を求めてください。 お寿司は一周回ってくることはないとする。

$N\leqq10^3$、$V[i]\leqq10^2$

yukicoder045

解法

DP.
$dp[i][0]:=i$番目を食べないときの美味しさの合計の最大値
$dp[i][1]:=i$番目を食べる　ときの美味しさの合計の最大値
とすると簡単に遷移できる。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    using VL = vector<LL>;        using VVL = vector<VL>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL N;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI v(N);
    
        FOR(i, 0, N) {
            cin >> v[i];
        }
        VVL dp(N + 1, VL(2, 0));
        FOR(i, 0, N) {
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + v[i]);
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][1]);
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][0]);
        }
        ans = max(dp[N][0], dp[N][1]);
    
        cout << ans << "\n";
    
        return 0;
    }