---

题目描述

题目译自 2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4 「방송국」

有 $N$ 个广播站，分别是 $s_{1}, s_{2}, \ldots, s_{N}$，它们位于一条直线上。广播站 $s_{i}$ 的位置是正整数 $x_{i}$。你需要为每个广播站 $s_{i}$ 分配广播信号的范围 $r_{i}$。当广播站 $s_{i}$ 进行广播时，距离 $s_{i}$ 不超过 $r_{i}$ 的广播站可以接收到 $s_{i}$ 的广播信号。换句话说，如果广播站 $s_{j}$ 位于闭区间 $\left[ x_{i} - r_{i}, x_{i} + r_{i} \right ]$ 内，那么 $s_{j}$ 就能接收到 $s_{i}$ 的广播信号。

广播站 $s_{i}$ 的广播可以通过 $h - 1$ $(h > 1)$ 个其他广播站传递给广播站 $s_{j}$。也就是说，存在广播站 $s_{i_{1}}, s_{i_{2}}, \ldots, s_{i_{h-1}}$，使得 $s_{i}$ 的广播传递给 $s_{i_{1}}$，每个 $s_{i_{k}}$ 再传递给 $s_{i_{k+1}}$，最后 $s_{i_{h-1}}$ 传递给 $s_{j}$，这样 $s_{i}$ 的广播在 $h$ 次传递内就可以到达 $s_{j}$。当然，当 $h=1$ 时，表示 $s_{i}$ 的广播直接传递给 $s_{j}$。在这些情况下，我们称 $s_{i}$ 的广播在 $h$ 步内传递到了 $s_{j}$。

我们希望选择一个广播站作为 $h$-集中站。这个广播站不进行广播，但必须能够在最多 $h$ 步内接收到其他所有广播站的广播。我们可以将 $h$-集中站的广播信号范围设为 $0$。

当为每个广播站 $s_{i}$ 分配广播范围 $r_{i}$ 时，分配成本定义为广播范围的平方和。也就是说，成本为

$$\sum_{i=1}^{N} r_{i}^{2}$$。我们将以最小化这个成本来分配广播范围。如果广播站 $s$ 作为 $h$-集中站时的最小分配成本为 $C_{h}^{*}(s)$，那么问题的目标就是在所有可能的 $h$-集中站 $s$ 中，找到具有最小 $C_{h}^{*}(s)$ 的那个，以及给出导致该最小成本的广播范围分配。 给定 $N$ 个广播站的位置，对于每个 $h=1, 2, \ldots, N-1$，编写一个程序，输出所有可能的 $h$-集中站 $s$ 的最小分配成本 $C_{h}^{*}(s)$ 中的最小值。 例如，下面的图 1 和图 2 是 $5$ 个广播站 $s_{1}, \ldots, s_{5}$，它们分别位于坐标 $1, 3, 4, 6, 9$，当 $h=2$ 时的情况。 在图 1 中，当为 $s_{1}, s_{2}, s_{3}, s_{4}$ 分别分配广播范围 $3, 1, 5, 2$，且 $s_{5}$ 作为 $2$-集中站时，最小成本为 $39$。 在图 2 中，当为 $s_{1}, s_{2}, s_{4}, s_{5}$ 分别分配广播范围 $2, 1, 2, 3$，且 $s_{3}$ 作为 $2$-集中站时，最小成本为 $18$。 因此，$18$ 是所有可能的 $2$-集中站的最小成本中的最小值。  **图 1**  **图 2** 你需要为管理员实现以下一个函数： ```cpp void stations(int N, int X[]); ``` 接受广播站的数量 $N$ 和每个广播站的位置 `X[0..N-1]` 作为参数。其中，`X[]` 是大小为 $N$ 的向量（vector），`X[i]` 的值互不相同，且按升序存储。 你需要在 `stations()` 函数中使用以下函数来提交答案： ```cpp void answer(long long Y[]); ``` 这是一个提交大小为 $N - 1$ 的向量 `Y[]` 的函数。对于 $i = 0, \ldots, N - 2$，`Y[i]` 的值是所有可能的 $(i + 1)$-集中站的最小成本的最小值。这个函数必须在 `stations()` 函数中且只能被调用一次。 --- ## 实现细节 你需要提交一个名为 `stations.cpp` 的文件。该文件必须实现以下函数： ```cpp void stations(int N, int X[]); ``` 该函数必须按照上述描述进行操作。当然，你可以创建和使用其他函数，但不得进行任何输入输出操作或访问其他文件。 --- ## 示例评测程序 示例评测程序按照以下格式读取输入： - 第 $1$ 行：$N$，其中 $N$ 表示广播站的数量 - 第 $2$ 行：$N$ 个整数 $x_{1}\,x_{2}\,\cdots\,x_{N}$ ，其中 $x_{i}$ 为广播站的位置 示例评测程序对于每个 $i = 1, \ldots, N - 1$，在第 $i$ 行输出所有可能的 $i$-集中站的最小成本的最小值。 --- ## 样例 1 **输入** ``` 3 1 3 8 ``` **输出** ``` 29 29 ``` --- ## 样例 2 **输入** ``` 5 1 3 4 6 9 ``` **输出** ``` 39 18 18 18 ``` --- ## 数据范围与提示 对于所有输入数据，满足： - $2 \leq N \leq 120$ - $1 \leq x_{1} < x_{2} < \cdots < x_{N} \leq 10^{8}$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | |--------|------|----------| | 1 | $11$ | $N \leq 7$ | | 2 | $21$ | $N \leq 30$ | | 3 | $17$ | $N \leq 60$ | | 4 | $51$ | 无附加限制 |$$