P14374 [JOISC 2018] 糖果 / Candies

桌上有 $N$ 颗糖果排成一排。每颗糖果都有一个称为 **美味值** 的值。从左数第 $i$ 颗糖果的美味值为 $A_i$（$1 \le i \le N$）。 JOI-chan 决定吃掉其中一部分糖果。她希望最大化所吃糖果的美味值总和。 然而，JOI-chan 认为仅贪心地选择糖果并不有趣，因此她制定了一条规则：她不能同时选择两颗相邻的糖果。 JOI-chan 尚未决定要吃多少颗糖果，因此她想知道，对于每个 $j$（$1 \le j \le \lceil \frac{N}{2} \rceil$），当她吃掉 $j$ 颗糖果时，所能获得的最大美味值总和是多少。这里 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。 **任务** 给定糖果数量和每颗糖果的美味值，编写一个程序，计算对于每个 $j$（$1 \le j \le \lceil \frac{N}{2} \rceil$），当她吃掉 $j$ 颗糖果时，所能获得的最大美味值总和。

从标准输入读取以下数据： - 输入第一行包含一个整数 $N$。这表示桌上有 $N$ 颗糖果。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $A_i$。这表示从左数第 $i$ 颗糖果的美味值为 $A_i$。

向标准输出写入 $\lceil \frac{N}{2} \rceil$ 行。第 $j$ 行（$1 \le j \le \lceil \frac{N}{2} \rceil$）输出当她吃掉 $j$ 颗糖果时所能获得的最大美味值总和。

### 样例 1 解释 在样例输入 1 中，共有 5 颗糖果，从左至右的美味值分别为 3、5、1、7、6。JOI-chan 应按如下方式吃糖果： - 当她吃 1 颗糖果时，她吃从左数第 4 颗糖果（美味值为 7）。 - 当她吃 2 颗糖果时，她吃从左数第 2 颗和第 4 颗糖果（美味值为 5、7）。 - 当她吃 3 颗糖果时，她吃从左数第 1 颗、第 3 颗和第 5 颗糖果（美味值为 3、1、6）。 再次强调，她不能同时选择两颗相邻的糖果。例如，请记住当她吃 2 颗糖果时，她不能同时吃从左数第 4 颗和第 5 颗糖果（美味值为 7、6）。 ### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 200\,000$。 - $1 \le A_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 ### 子任务 共有 2 个子任务。每个子任务的得分及附加约束如下： **子任务 1 [8 分]** - $N \le 2\,000$。 **子任务 2 [92 分]** 无额外约束。 翻译由 Qwen3-235B 完成