想定と違う解法っぽい。
問題リンク
問題概要
N要素の数列Aが与えられる。このうち互いに隣り合わないfloor(N/2)個の要素の和の最大値を求めよ。
解法
取る要素のうちほとんどは1つおきに並ぶことがわかる。
Nの偶奇によって場合分けをする。
あらかじめAの偶数番目の要素のみの累積和evensum、奇数番目のみの累積和oddsumをとっておく。
Nが偶数の場合：
取る要素を1、取らない要素を_で表すと
1_1_1_1__1_1_1_1
のように途中までは奇数番目のみ、途中からは偶数番目のみをとるので、
その境目をN/2+1通り試せば良い。
Nが奇数の場合：
取る要素は
1_1_1_1_1__1_1_1_1__1_1_1
のように序盤・終盤が奇数番目のみ、中盤が偶数番目のみとなるような和になる。
(要素の個数を0個や1個のみにすると、取らない要素が3つ連続する場合や取らない要素から始まる場合も含まれる)
境目をすべて探索するとO(N^2)になるので間に合わないが、次のように高速化できる。
i番目までの要素を赤から青に変換した時の和の変化量をs[i]とし、
\(t[j] = min(s[i]) (1 \leqq i \leqq j)\)
を更新しながら、右側の境目を左から探索していくことで
\(s[j] - s[i]\)の最大値を求めることができる。
提出
https://atcoder.jp/contests/abc162/submissions/11843019
感想
DPでも解けるみたいだけど、どっちでも細かいミスが怖い。
