Algorithm 版 (精华区)

发信人: GREnTOFEL (Crazy Plucking), 信区: Algorithm
标  题: 动态规划----石子归并(转载)
发信站: 哈工大紫丁香 (2002年07月06日21:52:34 星期六), 站内信件

【 以下文字转载自 Programming 讨论区 】
【 原文由 zjliu 所发表 】
发信人: violinist (巷战狙击手), 信区: Algorithm
标  题: 动态规划----石子归并
发信站: 日月光华 (Fri Jul  5 08:34:55 2002)

石子归并
〖题目描述〗
在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每

次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一

程序,由文件读入堆栈数N及每堆栈的石子数(<=20).
(!)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小;
(2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大;

输入数据:
第一行为石子堆数N;
第二行为每堆的石子数,每两个数之间用一个空格分隔.

输出数据:
从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合

并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺

时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示.

输入输出范例:
输入:
4
4 5 9 4
输出:
-4 5 9 -4
-8 -5 9
-13 -9
22

4 -5 -9 4
4 -14 -4
-4 -18
22




--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]




--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.229.154]