AtCoder Educational DP Contest C問題解いてみた

今回の問題

問題文
明日から太郎君の夏休みが始まります。太郎君は夏休みの計画を立てることにしました。

夏休みは $N$ 日からなります。各 $i$ $(1 \le i \le N)$ について、$i$ 日目には太郎君は次の活動のうちひとつを選んで行います。

• A: 海で泳ぐ。 幸福度 $a_i$ を得る。
• B: 山で虫取りをする。 幸福度 $b_i$ を得る。
• C: 家で宿題をする。 幸福度 $c_i$ を得る。

太郎君は飽き性なので、2日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n;
    cin >> n;
    int list[3][n];
    for(int i = 0; i < n; i++) {
        cin >> list[0][i] >> list[1][i] >> list[2][i];
    }
    int dp[n][3];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 3; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = list[0][0];
    dp[0][1] = list[1][0];
    dp[0][2] = list[2][0];
    for(int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + list[0][i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + list[1][i];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + list[2][i];
    }
    cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2])) << endl;
    return 0;
}

解説

dpではいらない情報を削除していくことが重要である。今回の場合は直前何を選んでいるのかしか重要ではないためそれ以外の情報はを削除している。dp[i][j]をi日目にjを選んだ時の幸福度の総和の最大値とする。漸化式はdp[i][j] = max(dp[i-1][j']+a[j'][i],dp[i-1][j'']+a[j''][i])のようになる。