2188: 宝典2第十一章合并魔法石2
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:7
Solved:4
Description
【题目描述】合并魔法石2 (merge2.cpp/c/pas)
魔法世界的魔法师曾经因臭氧层破坏而制造出覆盖整个星球大气层,用于抵御超量紫外线辐射的“天幕”。所以虽然太空防御系统是魔法世界历史上空前绝后的一项超大工程。但是具体实施起来并不是很困难,它其实是一个围绕整个星球赤道的圆形防御圈,圆形防御圈四周摆放N堆魔法石(N≤100),现要将魔法石有次序地合并成一堆。规定每次只能选相邻的两堆合并成一堆,并将新的一堆的魔法石数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆魔法石数(≤20),使得:
(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少;
(2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大。
【输入格式】
第一行为石子堆数N;
第二行为每堆石子数,每两个数之间用一空格分隔。
【输出格式】
两个数,即最大合并数和最小合并数。
【输入样例】
4
4 5 9 4
【输出样例】
54 43