Educational DP Contest C - Vacation

問題概要

問題のリンク

太郎君は$N$日間、毎日以下の$A, B, C$いずれかの活動を行う。

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

2日以上同じ活動を行うことはできない。この時、幸福度の最大値を求めよ。

制約条件

• 入力はすべて整数である。
• $1≤N≤10^5$
• $1≤a_i,b_i,c_i≤10^4$

考えたこと

2日以上同じ活動は不可能なので例えば、
1日目：10 40 70
2日目：20 50 80
3日目：30 60 90
となっていた場合Cの値、70, 80, 90を連続で取ることは不可能。
なので一つ前の処理でどの値をとったかインデックスを記録していこうと思ったがめんどくさそうだったので、2次元配列を作り、A,B,C全ての活動に対してその日行った場合の幸福度を求めた。
そうすれば前の日に行われたのはその日の活動を除いた二つのうち大きい方となるので。例えばその日Aを行った場合、前の日はBとCのうち大きい方を行っている。

よって以下のような遷移をさせる。

dp[i] = {a[i]+max(b[i-1],c[i-1]), 
         b[i]+max(a[i-1],c[i-1]), 
         c[i]+max(a[i-1],b[i-1])}

この時計算量は$O(N)$

解答

c.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<vector<int>> abc(n, vector<int>(3));
    for(int i = 0; i < n; i ++) cin >> abc[i][0] >> abc[i][1] >> abc[i][2];
    vector<vector<int>> dp(n, vector<int>(3));
    dp[0] = {abc[0][0], abc[0][1], abc[0][2]};
    for(int i = 1; i < n; i++) {
        dp[i] = {abc[i][0]+max(dp[i-1][1], dp[i-1][2]), abc[i][1]+max(dp[i-1][0], dp[i-1][2]), abc[i][2]+max(dp[i-1][0], dp[i-1][1])};
    }
    cout << *max_element(dp[n-1].begin(), dp[n-1].end()) << endl;
}