P17474 [ICPC 2018 Jiaozuo R] Distance
题目描述
在一条水平直线上有 $n$ 个点，从左至右依次标号为 $1$ 到 $n$。
第 $i$ 个点与第 $(i + 1)$ 个点之间的距离为 $a_i$。
对于每个从 $1$ 到 $n$ 的整数 $k$，你需要恰好选择 $k$ 个不同的给定点，使得所有被选中点对之间的距离之和最大。
输入格式
输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多可达 $1000$。
对于每组测试数据，第一行包含一个整数 $n$，表示点的数量，满足 $2 \leq n \leq 10^5$。
第二行包含 $(n - 1)$ 个正整数 $a_1, a_2, \cdots, a_{n - 1}$，满足 $1 \leq a_i \leq 10^4$。
我们保证所有测试数据中 $n$ 的总和不超过 $10^6$。
输出格式
对于每组测试数据，输出一行包含 $n$ 个整数，其中第 $i$ 个整数表示当 $k = i$ 时的最大距离之和。你应在相邻两个整数之间恰好输出一个空格，并避免该行出现任何末尾空格。
说明/提示
下图描述了该样例测试数据。
:::align{center}
:::
对于 $k = 2$，唯一的最优选择应选取最左侧与最右侧的点；而对于 $k = 3$，一种可能的最优选择可额外包含中间的任意一点。
翻译由 DeepSeek V4 Pro 完成