ABC162 F - Select Half (600)
Nが偶数の場合の取り方は以下の三つ
偶数要素だけ取る
奇数要素だけ取る
左からいくつかは偶数要素、右から奇数要素を取る
これらの内、最大になるのを求めれば良い
Nが奇数の場合はDPで解く
$ dp[i番目まで見た時に][必要以上にj個飛ばした] 時の最大の数
飛ばせる要素は2つなので$ O(N)で解けるDP
$ \max(dp[n-1][0], dp[n-2][1], dp[n-3][2]) が答え
遷移は、$ dp[i][j] = a[i] + max({dp[i-2][j], dp[i-3][j-1], dp[i-4][j-2]});
$ i, jで条件が不適切な物は適宜外す