[AtCoder] Educational DP Contest C – Vacation

問題

方針

動的計画法

前日とは同じ行動を取ることができないことに注意して考えます。\( 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]\) の最大値が答えになります。

コード