CF178A3 Educational Game

ABBYY 的聪明海狸开始开发一款新的儿童教育游戏。游戏规则非常简单，具体如下。 游戏场地是一串长度为 $n$ 的非负整数 $a_{i}$，编号从 $1$ 到 $n$。游戏的目标是用最少的操作次数，将前 $k$ 个数 $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$ 个元素 $a_{i}$ 全部变为零所需的最小操作次数。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。推荐使用 cin、cout 流或 %I64d 格式。

由 ChatGPT 4.1 翻译