C - Vacation

キーワード

DP
EDPC

解説

$i = 0,1,\dots,n, ~ j = 0,1,2$ に対して $dp_{i,j}$ を次のように定義する。

$i$ 日目に $j$ の活動を選んだときの幸福度の最大値

0 日目(夏休みに入る前)は何もしていないので、 $dp_{0,0} = dp_{0,1} = dp_{0,2} = 0$ とする。

$i$ 日目に $j$ の活動を選ぶことができるのは、 $i-1$ 日目に $j$ 以外の二つの場合のいずれか。 $dp_{i,j}$ は、 $i-1$ 日目に $j$ 以外の二つの活動を選んだときの幸福度の最大値に、 $i$ 日目に $j$ の活動を選んだときの幸福度を加えたものの最大値。

つまり、次のような漸化式が立てられる。

\begin{align} dp_{i,0} &= \max\{dp_{i-1,1} + b_i, dp_{i-1,2} + c_i\} \notag \\ dp_{i,1} &= \max\{dp_{i-1,0} + a_i, dp_{i-1,2} + c_i\} \notag \\ dp_{i,2} &= \max\{dp_{i-1,0} + a_i, dp_{i-1,1} + b_i\} \notag \\ \end{align}

最終的な答えは、 $\max\{dp_{n,0}, dp_{n,1}, dp_{n,2}\}$ 。

提出コード

int main() {
    int n; cin >> n;
    vector<vector<int>> DP(n+1, vector<int>(3));
    rep(i, 1, n+1) {
        int a, b, c; cin >> a >> b >> c;
        DP[i][0] = a + max(DP[i-1][1], DP[i-1][2]);
        DP[i][1] = b + max(DP[i-1][0], DP[i-1][2]);
        DP[i][2] = c + max(DP[i-1][0], DP[i-1][1]);
    }
    cout << max({DP[n][0], DP[n][1], DP[n][2]}) << endl;
}

B - Frog 2 D - Knapsack 1