[AtCoder] Educational DP Contest C – Vacation

2019年10月31日

問題

方針

動的計画法

前日とは同じ行動を取ることができないことに注意して考えます。\( i \) 日目に行動 \( j = \{A, B, C\}\) を取った時の最大値を \( d(i, j) \) とします。このときの遷移式は、

\[\begin{eqnarray}
d(i + 1, A) &=& a[i] + \max(d(i, B) , d(i, C))\\
d(i + 1, B) &=& b[i] + \max(d(i, A) , d(i, C))\\
d(i + 1, C) &=& c[i] + \max(d(i, A) , d(i, B))
\end{eqnarray}\]

となります。よって、\( dp[N][\cdot]\) の最大値が答えになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll a[N], b[N], c[N];
    ll dp[N + 1][3]{};
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    } 
    for (int i = 0; i < N; i++) {
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + a[i];
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + b[i];
        dp[i + 1][2] = max(dp[i][0], dp[i][1]) + c[i];
    }
    cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << "\n";
    return 0;
}