AT_joisc2018_j.飴 (Candies)

桌子上排列着编号从 $1$ 到 $n$ 的糖果，每颗糖果都有一个美味值 $a_{i}$。你不能同时吃相邻的两颗糖果。请你求出当你分别吃 $1,2,3,\ldots,\left \lceil \frac{n}{2} \right \rceil$ 颗糖果时，能够获得的美味值和的最大值。

第一行包含一个正整数 $n$。

接下来的 $n$ 行，每行一个整数，表示第 $i$ 颗糖果的美味值 $a_{i}$。

共输出 $\left \lceil \frac{n}{2} \right \rceil$ 行，第 $k$ 行表示当吃 $k$ 颗糖果时美味值和的最大值，$k$ 从 $1$ 到 $\left \lceil \frac{n}{2} \right \rceil$。

所有数据满足以下限制：

$1\le n\le 2\times 10^{5}$

$1\le a_{i}\le 10^{9}$

其中 $8\%$ 的数据满足：$1\le n\le 2000$

其余测试点无特殊限制。

【样例解释 #1】

只吃一颗糖果时，选择第 $4$ 颗，最大美味值为 $7$。

吃两颗糖果时，选择第 $2$ 颗和第 $4$ 颗最优，美味值为 $5+7=12$。

吃三颗糖果时，由于不能吃相邻的两颗糖果，只能选择第 $1$、第 $3$ 和第 $5$ 颗，美味值为 $3+1+6=10$。

由 ChatGPT 4.1 翻译