P9325 [CCC 2023 S2] Symmetric Mountains

Rebecca 是一名导游，正在为她的杂志推广落基山脉。她最近拍了一张包含 $N$ 座山的美丽照片，其中从左到右第 $i$ 座山的高度为 $h_i$。她将为她的杂志裁剪这张照片，可能会从照片的左侧移除一些山，也可能会从照片的右侧移除一些山。也就是说，裁剪包括从第 $l$ 座山到第 $r$ 座山的连续山峰，其中 $l \leq r$。为了取悦她的杂志读者，Rebecca 将尝试找到最对称的裁剪。 我们将裁剪的不对称值定义为从裁剪的中点开始，每对等距山峰的高度差的绝对值之和。为了帮助理解这个定义，注意到一个数 $v$ 的绝对值，记为 $|v|$，是 $v$ 的非负值：例如 $|-6| = 6$ 和 $|14| = 14$。裁剪的不对称值是所有 $|h_{l+i} - h_{r-i}|$ 的和，其中 $0 \leq i \leq \frac{r-l}{2}$。换句话说，我们从外向内配对山峰，计算每对山峰高度差的绝对值，并将它们相加。 因为 Rebecca 不知道照片需要多宽，所以对于所有可能的裁剪长度，找到不对称值最小的裁剪（即最对称的裁剪）。

第一行由一个整数 $N$ 组成，表示照片中山的数量。 第二行由 $N$ 个以空格分隔的整数组成，其中从左到右第 $i$ 个整数表示 $h_i$。 下表显示了可用的 15 分的分配方式： | 分数 | $N$ 的范围 | $h_i$ 的范围 | 额外限制 | | :-----------: | :-----------: | :-----------: | :-----------: | | $5$ | $1 \leq N \leq 300$ | $0 \leq h_i \leq 10^5$ | 无。 | | $5$ | $1 \leq N \leq 5000$ | $0 \leq h_i \leq 10^5$ | 山的高度从左到右单调不减。 | | $5$ | $1 \leq N \leq 5000$ | $0 \leq h_i \leq 10^5$ | 无。 |

输出一行 $N$ 个以空格分隔的整数，其中从左到右第 $i$ 个整数是长度为 $i$ 的裁剪中最对称的裁剪的不对称值。

对样例输入 1 的输出解释： 我们将展示为什么从左数第五个值是 2。让我们尝试计算所有长度为 5 的裁剪的不对称值。 第一个裁剪中山的高度是 $[3, 1, 4, 1, 5]$。这个裁剪的不对称值是 $|3 - 5| + |1 - 1| + |4 - 4| = 2$。 第二个裁剪中山的高度是 $[1, 4, 1, 5, 9]$。这个裁剪的不对称值是 $|1 - 9| + |4 - 5| + |1 - 1| = 9$。 最后一个裁剪中山的高度是 $[4, 1, 5, 9, 2]$。这个裁剪的不对称值是 $|4 - 2| + |1 - 9| + |5 - 5| = 10$。 因此，长度为 5 的最对称裁剪是不对称值为 2 的裁剪。 对样例输入 2 的输出解释： 这个样例满足第二个子任务。注意，唯一长度为 4 的裁剪是 $[1, 3, 5, 6]$，其不对称值为 $|1 - 6| + |3 - 5| = 7$。 **本题采用捆绑测试**： - 子任务 1（5 分）：$1\leq N \leq 300$，$0\leq h_i \leq 10^5$。 - 子任务 2（5 分）：$1 \leq N \leq 5000$，$0 \leq h_i \leq 10^5$，保证山的高度从左到右单调不减。 - 子任务 3（5 分）：$1\leq N\leq 5000$，$0 \leq h_i \leq 10^5$。 题面翻译由 ChatGPT-4o 提供。