【题目描述】18.9 合并石子2 (merge2)
N堆石子围成一圈,现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序读入堆数N及每堆石子数,使得:
(1)选择一种合并石子的方案,使得N-1次合并后,得分的总和最少;
(2)选择一种合并石子的方案,使得N-1次合并后,得分的总和最大。
第一行为石子堆数N(N≤2500);
第二行为每堆石子数(≤2^{16}),每两个数之间用一空格分隔。
输出两个数,即最小合并数总和及最大合并数总和。
4 4 5 9 4
43 54
对于50\%的数据,N\leq 100,每堆石子数(≤20)