石子合并问题（求解将n堆石子合并为一堆时的最小与最大得分）
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
石子合并问题是算法设计中的经典案例，涉及将n堆石子通过连续合并最终形成单一的一堆。本题探讨在这一过程中实现最小化和最大化合并得分策略，考察动态规划的应用技巧及问题优化能力。
问题 F：石子合并
时间限制：1000MS 内存限制：65536K 总提交次数：1180 已接受次数：386 语言不限制
描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
例如，4堆石子每堆石子个数（从最上面的一堆开始顺时针方向）依次是 4、5、9 和 4，则3次合并后得分总和最小的方法如图所示，得分为43；而方法最大的情况为另一组合并方式，其得分为54。
编程任务：
对于给定n堆石子,计算出将它们合并成一堆的最小得分和最大得分。
输入格式:
第一行是正整数n（1<=n<=100），表示有n堆石子。
第二行为 n 个数字，分别代表每堆石子的数量。
输出格式：
程序结束时应输出两行，第1 行中的数是最小得分；第2 行中的数是最大得分。
样例输入:
4
4 5 9 4
样例输出:
43
54
全部评论 (0)
还没有任何评论哟~
