在一个圆形操场的四周摆放了n堆石子(n≤100),现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记为该次合并的得分。
编程,读入堆数n及每堆石子数(≤20),选择一种合并石子的方案,使得做n-1次合并,得分的总和最小;选择一种合并石子的方案,使得做n-1次合并,得分的总和最大。
例如,如图9.6-1所示的4堆石子,每堆石子数(从最上面的一堆开始按顺时针方向数)依次为4、5、9、4,则3次合并得分总和最小的方案如图9.6-2所示,得分总和最大的方案如图9.6-3所示。
第1行为石子堆数n,第2行为每堆石子数,每两个数之间用一个空格分隔。
第1行为最小得分值,第2行为最大得分值。
4 4 5 9 4
43 54
动规专题