石子合并(动态规划)详细解题报告 2007-02-25 14:58 一．试题 在一个园形操场的四周摆放N堆石子（N≤ 100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 编一程序，由文件读入堆数 N及每堆的石子数（≤ ２０）， ① 选择一种合并石子的方案，使得做 N－1次合并，得分的总和最小； ② 选择一种合并石子的方案，使得做 N－1次合并，得分的总和最大。 例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依 次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３ 得分最大的方案为：１４＋１８＋２２＝５４ 输入数据： 文件名由键盘输入，该文件内容为： 第一行为石子堆数 N； 第二行为每堆的石子数，每两个数之间用一个空格符分隔。 输出数据： 输出文件名为 output.txt 从第 1至第 N行为得分最小的合并方案。第 N＋1行是空行。从第 N＋2行到第 2N＋1行是得 分最大合并方案。 每种合并方案用 N行表示，其中第 i行（1≤ i≤ N）表示第 i 次合并前各堆的石子数（依 顺时针次序输出，哪一堆先输出均可）。 要求将待合并的两堆石子数以相应的负数表示，以便标识。 输入输出范例： 输入文件内容： ４ ４ ５９ ４ 输出文件内容： －４ ５ ９ －４ －８－５ ９ －１３ －９ ２２ ４ －５ －９ ４ ４ －１４ －４ －４－１８ ２２ 二．算法分析 竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面 的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小（最大）的相邻两堆合并， 形成新的一堆；接下来，在 N－1堆中选得分最小（最大）的相邻两堆合并„„，依次类推， 直至所有石子经 N－1次合并后形成一堆。 例如有６堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为３ ４６ ５ ４ ２ 要求选择一种合并石子的方案，使得做５次合并，得分的总和最小。 按照贪心法，合并的过程如下： 每次合并得分 第一次合并 ３ ４ ６ ５ ４ ２ ->５ 第二次合并 ５ ４ ６ ５ ４ ->９ 第三次合并 ９ ６ ５ ４ ->９ 第四次合并 ９ ６ ９ ->１５ 第五次合并 １５ ９ ->２４ 24 总得分＝５＋９＋９＋１５＋２４＝６２ 但是当我们仔细琢磨后，可得出另一个合并石子的方案： 每次合并得分 第一次合并 ３ ４...
