网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
合并魔法石2
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 12:30 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 12:30 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 12:30 |
输入文件 | merge2.in | 输出文件 | merge2.out |
【题目描述】合并魔法石2 (merge2.cpp/c/pas)
魔法世界的魔法师曾经因臭氧层破坏而制造出覆盖整个星球大气层,用于抵御超量紫外线辐射的“天幕”。所以虽然太空防御系统是魔法世界历史上空前绝后的一项超大工程。但是具体实施起来并不是很困难,它其实是一个围绕整个星球赤道的圆形防御圈,圆形防御圈四周摆放N堆魔法石(N≤100),现要将魔法石有次序地合并成一堆。规定每次只能选相邻的两堆合并成一堆,并将新的一堆的魔法石数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆魔法石数(≤20),使得:
(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少;
(2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大。
【输入格式】
第一行为石子堆数N;
第二行为每堆石子数,每两个数之间用一空格分隔。
【输出格式】
两个数,即最大合并数和最小合并数。
【输入样例】
4
4 5 9 4
【输出样例】
54 43