动态规划石子合并问题 【石子合并】 在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次 只能选相邻的 2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 试设计一个算法,计算出将 n 堆石子合并成一堆的最小得分和最大得分。 【输入文件】 包含两行,第 1 行是正整数 n(1<=n<=100),表示有 n 堆石子。 第 2 行有 n 个数,分别表示每堆石子的个数。 【输出文件】 输出两行。 第 1 行中的数是最小得分;第 2 行中的数是最大得分。 【输入样例】 4 4 4 5 9 【输出样例】 43 54 【分析】 本题初看以为可以使用贪心法解决问题, 但是事实上因为有必须相邻两堆才能合并这个 条件在,用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。 例如下面这个例子: 3 4 6 5 4 2 如果使用贪心法求最小得分,应该是如下的