K14151 石子 (stone)

题目描述

小可可面前有n堆石子，第i堆石子有ai个石子。小可可想要在开始选择一堆石子，然后从它开始，每次合并这堆石子左边的那堆石子或者右边的那堆石子。合并两堆石子个数为 x, y 的石子堆需要花x+y的力气，并且会合并成一堆x+y个石子的石子堆。              

小可可想花费最小的力气从最初选择的那堆石子开始，将所有石子都合并完。小可可想知道，如果他选择编号在 [l, r] 里面的每一堆石子作为最初的石子，那么他将n堆石子合并成一堆花的最小力气是多少。

小可可不想太为难你，所以他保证所有的ai是随机的。

输入格式 第一行输入一行三个整数 n, l, r，石子堆数和最开始选择的那堆石子的编号区间。 

第二行输入 n 个整数 a1, a2, · · · , an，表示每堆石子的石子个数。

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

输入输出样例

输入样例1：

4 1 4            

5 1 3 1                        

    

输出样例1：

25 19 19 19

说明

样例说明：

对于第 1 堆石子作为初始的石子堆，最优(也是唯一)的合并策略是先合并第 2 堆， 再合并第 3 堆，随后合并第 4 堆，花费力气为 25;   

对于第 2 堆石子作为初始的石子堆，最优的合并策略是先合并第 3 堆，再合并第 4 堆，随后合并第 1 堆，花费力气为 19;           

对于第 3 堆石子作为初始的石子堆，最优的合并策略是先合并第 2 堆，再合并第 4 堆，随后合并第 1 堆，花费力气为 19;                                      

对于第 4 堆石子作为初始的石子堆，最优(也是唯一)的合并策略是先合并第 3 堆，再合并第 2 堆，随后合并第 1 堆，花费力气为 19。                                 

数据规模与约定                            

对于 20% 的数据，满足 n ≤ 10;

对于 40% 的数据，满足 n ≤ 300;

对于 60% 的数据，满足 n ≤ 5000;

对于另外 20% 的数据，满足 n ≤ 10^5, r − l + 1 ≤ 50;

对于100%的数据，有1 ≤ l ≤ r ≤ n ≤ 10^5,1 ≤ ai ≤ 10^8。

保证ai 随机。

随机方式为:先选择一个所有 ai 的上界 v，对于每个 ai，它在 [1, v] 中的所有整数中等概率随机选取一个。