人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Educational DP Contest:C - Vacation

問題

atcoder.jp

解法

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).

解答

atcoder.jp

f:id:babcs2035:20190107164307p:plain