Educational DP Contest:C - Vacation
問題
解法
dp(i, j) := i - 1 日目に j を選んだ時の i 日目までの幸福度の和の最大
と定義する.このとき,
dp(i, j) = max( dp(i - 1, 0) + a_(i - 1) (j != 0 のとき), dp(i - 1, 1) + b_(i - 1) (j != 1 のとき), dp(i - 1, 2) + c_(i - 1) (j != 2 のとき))
と漸化式が立つ.状態数 O(N),遷移 O(1) となり O(N).
解答