CF178A2 Educational Game

来自 ABBYY 的聪明海狸开始开发一款新的儿童教育游戏。游戏规则相当简单，具体如下所述。 游戏场地是一串长度为 $n$ 的非负整数 $a_{i}$，编号从 $1$ 到 $n$。游戏的目标是用最少的操作次数，使得某个前缀 $a_{1},a_{2},...,a_{k}$（即前 $k$ 个数，$k 0$，再选择一个整数 $t$（$t \geq 0$），使得 $i+2^{t} \leq n$。选定 $i$ 和 $t$ 后，将 $a_{i}$ 减 $1$，同时将 $a_{i+2^{t}}$ 加 $1$。例如，若 $n=4$，$a=(1,0,1,2)$，可以选择 $i=3$，$t=0$，得到 $a=(1,0,0,3)$；或者选择 $i=1$，$t=1$，得到 $a=(0,0,2,2)$（唯一的其他可行操作是 $i=1$，$t=0$）。 给定 $n$ 和初始序列 $a_{i}$，你的任务是，对于每个可能的 $k$（$1 \leq k < n$），计算将原序列的前 $k$ 个元素全部变为零所需的最小操作次数。

第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $a_{i}$（$0 \leq a_{i} \leq 10^{4}$），用空格分隔。 获得 20 分的输入限制： - $1 \leq n \leq 300$ 获得 50 分的输入限制： - $1 \leq n \leq 2000$ 获得 100 分的输入限制： - $1 \leq n \leq 10^{5}$

输出恰好 $n-1$ 行，第 $k$ 行输出将原序列的前 $k$ 个元素全部变为零所需的最小操作次数。 请不要在 C++ 中使用 %lld 格式符来读写 64 位整数。建议使用 cin、cout 流，或 %I64d 格式符。

由 ChatGPT 4.1 翻译