U416539 [“科大国创杯”2023 年安徽省青少年信息学科普日-ACSPJ组] 石子

“科大国创杯”2023 年安徽省青少年信息学科普日-ACSPJ组第四题

小可可面前有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个石子。小可可想要在开始选择一堆石子，然后从它开始，每次合并这堆石子左边的那堆石子或者右边的那堆石子。合并两堆石子个数为 $x, y$ 的石子堆需要花 $x + y$ 的力气，并且会合并成一堆 $x + y$ 个石子的石子堆。 小可可想花费最小的力气从最初选择的那堆石子开始，将所有石子都合并完。小可可想知道，如果他选择编号在 $[l, r]$ 里面的每一堆石子作为最初的石子，那么他将 $n$ 堆石子合并成一堆花的最小力气是多少。 小可可不想太为难你，所以他保证所有的 $a_i$ 是随机的。

第一行输入一行三个整数 $n, l, r$，石子堆数和最开始选择的那堆石子的编号区间。 第二行输入 $n$ 个整数 $a_1, a_2, \cdots , a_n$，表示每堆石子的石子个数。

输出一行 $r - l + 1$ 个整数，第 $i$ 个整数表示小可可选择编号为 $l - 1 + i$ 的石子堆作为最开始的那堆石子时，将所有石子都合并完花的最少力气。

#### 样例1解释 对于第 $1$ 堆石子作为初始的石子堆，最优（也是唯一）的合并策略是先合并第 $2$ 堆，再合并第 $3$ 堆，随后合并第 $4$ 堆，花费力气为 $25$； 对于第 $2$ 堆石子作为初始的石子堆，最优的合并策略是先合并第 $3$ 堆，再合并第 $4$ 堆，随后合并第 $1$ 堆，花费力气为 $19$； 对于第 $3$ 堆石子作为初始的石子堆，最优的合并策略是先合并第 $2$ 堆，再合并第 $4$ 堆，随后合并第 $1$ 堆，花费力气为 $19$； 对于第 $4$ 堆石子作为初始的石子堆，最优（也是唯一）的合并策略是先合并第 $3$ 堆，再合并第 $2$ 堆，随后合并第 $1$ 堆，花费力气为 $19$。 ---------------------- #### 数据规模与约定 对于 $20\%$ 的数据，满足 $n \le 10$； 对于 $40\%$ 的数据，满足 $n \le 300$； 对于 $60\%$ 的数据，满足 $n \le 5000$； 对于另外 $20\%$ 的数据，满足 $n \le 10^5, r − l + 1 \le 50$； 对于 $100\%$ 的数据，有 $1 \le l \le r \le n \le 10^5, 1 \le a_i \le 10^8$。保证 $a_i$ 随机。随机方式为：先选择一个所有 $a_i$ 的上界 $v$，对于每个 $a_i$，它在 $[1, v]$ 中的所有整数中等概率随机选取一个。