【競プロ】1日1AC : EDPC C問題【動的計画法】

今日もEducational DP Contestの問題を解きます。まだまだ先は長いですが、問題を通してじっくり身につけていきましょう。

問題のリンクはこちら。

提出コードと考えたこと

DPを使う前提で考えれば、適当な配列dpを「ある日までの幸福度の総和」として考えればよいでしょう。A, B問題のように \(i\) 日目までの幸福度の総和として \( dp_i\) を考えたくなりますが、\(i\) 日目にどの活動ができるかは前日に何をしたかに左右されます。
よって \(dp^{j}_{i}\) を \( i \) 日目に行動 \(j\) をした時の、その日までの幸福度の総和とします。また、\(a_i,b_i,c_i\) は \(i\) 日目の活動 \(A,B,C\) で得られる幸福度とします。
（実装の都合上、\(0\) 日目から\(N-1\) 日目までを考えます。）

活動 \(A,B,C\) はそれぞれ活動 \(0,1,2\) として扱うことにします。ここで前回までと同じように、以下の式が成り立ちます。

\[dp^{0}_{i}=\max \{dp^{1}_{i-1},dp^{2}_{i-1}\} + a_{i} \]
\[dp^{1}_{i}=\max \{dp^{0}_{i-1},dp^{2}_{i-1}\} + b_{i} \]
\[dp^{2}_{i}=\max \{dp^{0}_{i-1},dp^{1}_{i-1}\} + c_{i} \]

ここで求めるべき答えは

\[\mathrm{ans}=\max \{dp^{0}_{N-1},dp^{1}_{N-1},dp^{2}_{N-1}\} \]

であることが分かりますね。これをそのまま実装します。

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

int N_MAX = 100000;
vector a(N_MAX),b(N_MAX),c(N_MAX);
vector<vector<int>> dp(N_MAX,vector<int>(3,0));

int main(){
    int N;
    cin >> N;
    for(int i = 0;i < N;i++) cin >> a[i] >> b[i] >> c[i];
    dp[0][0] = a[0]; dp[0][1] = b[0]; dp[0][2] = c[0];
    for(int i = 1;i < N;i++){
        dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c[i];
    }
    int ans = max(dp[N-1][0],max(dp[N-1][1],dp[N-1][2]));
    cout << ans << endl;
    return 0;
}

12行目の初期条件を忘れないようにしましょう。