yukicoder No.258 回転寿司(2)

問題

問題概要

N個の寿司が並んでいる。順番に食べていくが、連続して食べることはできない。寿司にはおいしさがそれぞれ決まっている。食べた寿司のおいしさの合計の最大値を求めよ。またどの寿司を食べたかも求める。経路復元。

解法

動的計画法で解く。dp[i][j] := i番目のお寿司までを考えて、j=1の時は、i番目の寿司を食べ、j=0の時は、i番目の寿司を食べていない と定めて、dp[0][0] = 0からループで回していく。
j == 0の時は
dp[i + 1][0] = max(dp[i + 1][0], dp[i][0]) 食べない　-(1)
dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + v[i]) 食べる -(2)
j == 1の時は
dp[i + 1][0] = max(dp[i + 1][0], dp[i][1]) 食べれない -(3)
のような漸化式がなりたつ。
またこの問題は経路復元をしなければならないが、上で用いた漸化式を使い、i = nの時から、逆方向に調べていけば、どの寿司を食べたかはわかる。

ミス

dpの経路復元はすこし難しい。また、dpの配列も1次元で行けるみたいだね。 dp[i] = max(dp[i - 1], dp[i - 2] + v[i])のような漸化式を使えば?

コード

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, v[1010];
//dp[i][j] := i番目のお寿司までを考えて、j=1の時は、i番目の寿司を食べ、
//j=0の時は、i番目の寿司を食べていない

int dp[1010][2];
int main(void){
    int n, v[1010];
    cin >> n;
    rep(i, n) cin >> v[i];
    rep(i, 1010)rep(j, 2) dp[i][j] = 0;

    for (int i = 0; i < n; ++i){
        for (int j = 0; j < 2; ++j){
            if(j == 0){//前回の寿司を食べていない
                dp[i + 1][0] = max(dp[i + 1][0], dp[i][0]);//食べない　-(1)
                dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + v[i]);//食べる -(2)
            }else{
                dp[i + 1][0] = max(dp[i + 1][0], dp[i][1]);//食べれない -(3)
            }
        }
    }

    int ans, f;
    vector<int> g;
    if(dp[n][0] > dp[n][1]){
        ans = dp[n][0];
        f = 0;
    }else{
        ans = dp[n][1];
        f = 1;
        g.push_back(n);
    }

    //dpの漸化式を逆にたどる
    for (int i = n - 1; i >= 0; --i){
        if(f == 0){//次は、f=0 or f=1
            if(dp[i + 1][f] == dp[i][0]){//i番目を食べない -(1)s
                f = 0;
            }else if(dp[i + 1][f] == dp[i][1]){//i - 1番目を食べる -(3)
                f = 1;
                g.push_back(i);
            }
        }else{//次は、f=0
            if(dp[i + 1][1] = dp[i][0] + v[i]){//i番目を食べる　-(2)
                f = 0;
            }
        }
    }
    reverse(g.begin(), g.end());

    printf("%d\n", ans);
    rep(i, g.size()){
        printf("%d ", g[i]);
    }
    printf("\n");
    return 0;
}