P12585 「KTSC 2019 R1」广播站

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include void stations(std::vector X); void answer(std::vector Ans); ``` 题目译自 [2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2019/) T4「[방송국](https://assets.ioikorea.kr/ioitst/2019/1/stations/stations_statement.pdf)」

有 $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$-集中站的最小成本中的最小值。 你需要为管理员实现以下一个函数： `void stations(int N, int X[]);` 接受广播站的数量 `N` 和每个广播站的位置 `X[0..N-1]` 作为参数。其中，`X[]` 是大小为 `N` 的向量（`vector`），`X[i]` 的值互不相同，且按升序存储。 你需要在 `stations()` 函数中使用以下函数来提交答案： `void answer(long long Y[]);` 这是一个提交大小为 `N - 1` 的向量 `Y[]` 的函数。对于 $i = 0, \ldots, N - 2$，`Y[i]` 的值是所有可能的 $(i + 1)$-集中站的最小成本的最小值。这个函数必须在 `stations()` 函数中且只能被调用一次。 该函数必须按照上述描述进行操作。当然，你可以创建和使用其他函数，但不得进行任何输入输出操作或访问其他文件。

示例评测程序按照以下格式读取输入： - 第 $1$ 行：$N$，其中 $N$ 表示广播站的数量 - 第 $2$ 行：$N$ 个整数 $x_{1}\,x_{2}\,\cdots\,x_{N}$，其中 $x_{i}$ 为广播站的位置

示例评测程序对于每个 $i = 1, \ldots, N - 1$，在第 $i$ 行输出所有可能的 $i$-集中站的最小成本的最小值。

### 数据范围 对于所有输入数据，满足： - $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$|无附加限制|