ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

2019-01-31

Educational DP Contest / DP まとめコンテスト C - Vacation

解法

$dp[i][j] = i$ 日目に行動 $j$ を選択(0:A,1:B,2:C)したときの $1$ ～ $i$ 日までの幸福度の合計の最大値
とします。
すると、
$j=0$ のとき $dp[i][j] = max(dp[i-1][1] + a_{i},dp[i-1][2] + a_{i})$
$j=1$ のとき $dp[i][j] = max(dp[i-1][0] + a_{i},dp[i-1][2] + b_{i})$
$j=2$ のとき $dp[i][j] = max(dp[i-1][0] + a_{i},dp[i-1][1] + c_{i})$
となります。
あとは、これをもとに計算をし、 $dp[N][j]$ の最大値を選べば答えになります。