ABC162 F - Select Half (600)
解答：Submission #13466424 - AtCoder Beginner Contest 162
解法： こちらのブログを参考にしました。考察が綺麗すぎて感動です。 betrue12.hateblo.jp
まず、連続しないぎりぎりで数を選ぶことを考えます。oxoxoxoのような選び方です。
次に、この状態からいくつxを増やすことができるかを考えます。上記の場合oが4つですので、n=8, 9になります。
n=8の場合は1つ、9の場合は2つ×を増やすことができます。実はnの大きさによらず、nが偶数であればxを1つ、奇数であればxを2つ増やすことができます。この性質を利用して次のようなdpを考えます。
dp[i][j]：i番目の数まで見ていて、余分に増やしたxの数がj個であるときのAの和の最大値
このときdp[i][j]はdp[i+2][j]+A[i+2]、dp[i+3][j+1] + A[i+3]、dp[i+4][j+2] + A[i+4]に遷移します。oにするときしかdpは遷移させません。
直前のoがiであったとき、i+1でoにすることはできないので、i+1には遷移しません。i+2でoにするときは余分に増やしたxの数は変わりませんのでjのままです（詰め詰めの状態）。i+3でoにするときはxを余分に1つ増やすことになりますのでj+1です。i+4のときは2つ増えるのでj+2です。
最終的にどこを採用するかについてです。 偶数の場合は、...oxで終わるか...xoで終わるかのいずれかですので、dp[n-2][0]かdp[n-1][1]かのいずれかです。 奇数の場合は、...oxxで終わるか、...xoxで終わるか、...xoで終わるかのいずれかですので、dp[n-3][0]かdp[n-2][1]かdp[n-1][2]かのいずれかです。
