一．試題

??????在一個(gè)園形操場(chǎng)的四周擺放N堆石子（N≤100），現(xiàn)要將石子有次序地合并成一堆。規(guī)定

??????每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。

??????編一程序，由文件讀入堆數(shù)N及每堆的石子數(shù)（≤２０），

??????①選擇一種合并石子的方案，使得做N－1次合并，得分的總和最小；

??????②選擇一種合并石子的方案，使得做N－1次合并，得分的總和最大。

??????例如，所示的４堆石子，每堆石子數(shù)（從最上面的一堆數(shù)起，順時(shí)針數(shù)）依

??????次為４５９４。則３次合并得分總和最小的方案：８＋１３＋２２＝４３

??????得分最大的方案為：１４＋１８＋２２＝５４

??????輸入數(shù)據(jù)：

??????文件名由鍵盤輸入，該文件內(nèi)容為：

??????第一行為石子堆數(shù)N；

??????第二行為每堆的石子數(shù)，每?jī)蓚€(gè)數(shù)之間用一個(gè)空格符分隔。

??????輸出數(shù)據(jù)：

??????輸出文件名為output.txt

??????從第1至第N行為得分最小的合并方案。第N＋1行是空行。從第N＋2行到第2N＋1行是得

??????分最大合并方案。

??????每種合并方案用N行表示，其中第i行（1≤i≤N）表示第i 次合并前各堆的石子數(shù)（依

??????順時(shí)針次序輸出，哪一堆先輸出均可）。 要求將待合并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示，以便標(biāo)識(shí)。

??????輸入輸出范例：

??????輸入文件內(nèi)容：

??????４

??????４ ５９ ４

??????輸出文件內(nèi)容：

??????－４ ５ ９ －４

??????－８－５ ９

??????－１３ －９

??????２２

???????

??????４ －５ －９ ４

??????４ －１４ －４

??????－４－１８

??????２２

??????二．算法分析

??????競(jìng)賽中多數(shù)選手都不約而同地采用了盡可能逼近目標(biāo)的貪心法來(lái)逐次合并：從最上面

??????的一堆開(kāi)始，沿順時(shí)針?lè)较蚺懦梢粋€(gè)序列。 第一次選得分最小（最大）的相鄰兩堆合并，

??????形成新的一堆；接下來(lái)，在N－1堆中選得分最小（最大）的相鄰兩堆合并……，依次類推，

??????直至所有石子經(jīng)N－1次合并后形成一堆。

??????例如有６堆石子，每堆石子數(shù)（從最上面一堆數(shù)起，順時(shí)針數(shù)）依次為３ ４６ ５ ４ ２

??????要求選擇一種合并石子的方案，使得做５次合并，得分的總和最小。

??????按照貪心法，合并的過(guò)程如下：

??????每次合并得分

??????第一次合并 ３ ４ ６ ５ ４ ２ ->５

??????第二次合并 ５ ４ ６ ５ ４ ???->９

??????第三次合并 ９ ６ ５ ４ ??????->９

??????第四次合并 ９ ６ ９ ?????????->１５

??????第五次合并 １５ ９ ??????????->２４

??????24

??????總得分＝５＋９＋９＋１５＋２４＝６２

??????但是當(dāng)我們仔細(xì)琢磨后，可得出另一個(gè)合并石子的方案：

??????每次合并得分

??????第一次合并 ３ ４ ６ ５ ４ ２ ?->７

??????第二次合并 ７ ６ ５ ４ ２ ????->１３

??????第三次合并 １３ ５ ４ ２ ?????->６

??????第四次合并 １３ ５ ６ ????????->１１

??????第五次合并 １３ １１ ?????????->２４

??????24

??????總得分＝７＋６＋１１＋１３＋２４＝６１

??????顯然，后者比貪心法得出的合并方案更優(yōu)。 題目中的示例故意造成一個(gè)貪心法解題的

??????假像，誘使讀者進(jìn)入“陷阱”。為了幫助讀者從這個(gè)“陷阱”里走出來(lái)， 我們先來(lái)明確一個(gè)問(wèn)題：

??????１．最佳合并過(guò)程符合最佳原理

??????使用貪心法至所以可能出錯(cuò)，

??????是因?yàn)槊恳淮芜x擇得分最小（最大）的相鄰兩堆合并，不一定保證余下的合并過(guò)程能導(dǎo)致最優(yōu)解。聰明的讀者馬上會(huì)想到一種理想的假設(shè)：如果N－1次合并的全局最優(yōu)解包含了每一次合并的子問(wèn)題的最優(yōu)解，那么經(jīng)這樣的N－1次合并后的得分總和必然是最優(yōu)的。

??????例如上例中第五次合并石子數(shù)分別為１３和１１的相鄰兩堆。

??????這兩堆石頭分別由最初的第１，２，３堆（石頭數(shù)分別為３，４，６）和第４，５，６堆（石頭數(shù)分別為５，４，２）經(jīng)４次合并后形成的。于是問(wèn)題又歸結(jié)為如何使得這兩個(gè)子序列的N－2

??????次合并的得分總和最優(yōu)。為了實(shí)現(xiàn)這一目標(biāo)，我們將第１個(gè)序列又一分為二：第１、２堆構(gòu)成子序列１，

??????第３堆為子序列２。第一次合并子序列１中的兩堆，得分７；

??????第二次再將之與子序列２的一堆合并，得分１３。顯然對(duì)于第１個(gè)子序列來(lái)說(shuō)，這樣的合并方案是最優(yōu)的。同樣，我們將第２個(gè)子序列也一分為二；第４堆為子序列１，第５，６堆構(gòu)成子序列２。第三次合并子序列２中的２堆，得分６；第四次再將之與子序列１中的一堆合并，得分１３。顯然對(duì)于第二個(gè)子序列來(lái)說(shuō)，這樣的合并方案也是最優(yōu)的。

??????由此得出一個(gè)結(jié)論──６堆石子經(jīng)

??????過(guò)這樣的５次合并后，得分的總和最小。我們把每一次合并劃分為階段，當(dāng)前階段中計(jì)算出的得分和作為狀態(tài)，

??????如何在前一次合并的基礎(chǔ)上定義一個(gè)能使目前得分總和最大的合并方案作為一次決策。很顯然，某階段的狀態(tài)給定后，則以后各階段的決策不受這階段以前各段狀態(tài)的影響。

??????這種無(wú)后效性的性質(zhì)符最佳原理，因此可以用動(dòng)態(tài)規(guī)劃的算法求解。

??????２．動(dòng)態(tài)規(guī)劃的方向和初值的設(shè)定

??????采用動(dòng)態(tài)規(guī)劃求解的關(guān)鍵是確定所有石子堆子序列的最佳合并方案。 這些石子堆子序列包括：

??????｛第１堆、第２堆｝、｛第２堆、第３堆｝、……、｛第N堆、第１堆｝；

??????｛第１堆、第２堆、第３堆｝、｛第２堆、第３堆、第４堆｝、……、｛第N堆、第１堆、第２堆｝；……

??????｛第１堆、……、第N堆｝｛第１堆、……、第N堆、第１堆｝……｛第N堆、第１堆、……、第N－１堆｝

??????為了便于運(yùn)算，我們用〔i，j〕表示一個(gè)從第i堆數(shù)起，順時(shí)針數(shù)j堆時(shí)的子序列｛第i堆、第i＋１堆、……、第（i＋j－1）mod n堆｝

??????它的最佳合并方案包括兩個(gè)信息：

??????①在該子序列的各堆石子合并成一堆的過(guò)程中，各次合并得分的總和；

??????②形成最佳得分和的子序列１和子序列２。由于兩個(gè)子序列是相鄰的， 因此只需記住子序列１的堆數(shù)；

??????設(shè)

??????f〔i，j〕──將子序列〔i，j〕中的j堆石子合并成一堆的最佳得分和；

??????c〔i，j〕──將〔i，j〕一分為二，其中子序列１的堆數(shù)；

??????（１≤i≤N，１≤j≤N）

??????顯然，對(duì)每一堆石子來(lái)說(shuō)，它的

??????f〔i，１〕＝０

??????c〔i，１〕＝０ （１≤i≤N）

??????對(duì)于子序列〔i，j〕來(lái)說(shuō)，若求最小得分總和，f〔i，j〕的初始值為∞； 若求最大得分總和，f〔i，j〕的初始值為０。（１≤i≤N，２≤j≤N）。

??????動(dòng)態(tài)規(guī)劃的方向是順推(即從上而下)。先考慮含二堆石子的N個(gè)子序列（各子序列分別從第１堆、第２堆、……、第N堆數(shù)起，順時(shí)針數(shù)２堆）的合并方案

??????f〔１，２〕，f〔２，２〕，……，f〔N，２〕

??????c〔１，２〕，c〔２，２〕，……，c〔N，２〕

??????然后考慮含三堆石子的Ｎ個(gè)子序列（各子序列分別從第１堆、第２堆、……、第Ｎ堆數(shù)起，順時(shí)針數(shù)３堆）的合并方案

??????f〔１，３〕，f〔２，３〕，……，f〔N，３〕

??????c〔１，３〕，c〔２，３〕，……，c〔N，３〕

??????……

??????依次類推，直至考慮了含N堆石子的N個(gè)子序列（各子序列分別從第１堆、第２堆、 ……、第N堆數(shù)起，順時(shí)針數(shù)N堆）的合并方案

??????f〔１，N〕，f〔２，N〕，……，f〔N，N〕

??????c〔１，N〕，c〔２，N〕，……，c〔N，N〕

??????最后，在子序列〔１，N〕，〔２，N〕，……，〔N，N〕中，選擇得分總和（f值）最小（或最大）的一個(gè)子序列〔i，N〕（１≤i≤N），由此出發(fā)倒推合并過(guò)程。

??????３．動(dòng)態(tài)規(guī)劃方程和倒推合并過(guò)程

??????對(duì)子序列〔i，j〕最后一次合并，其得分為第i堆數(shù)起，順時(shí)針數(shù)j堆的石子總數(shù)t。被合并的兩堆石子是由子序列〔i，k〕和〔（i＋k－１）mod

??????n＋１，j－k〕（１≤k≤j－１）經(jīng)有限次合并形成的。為了求出最佳合并方案中的k值，我們定義一個(gè)動(dòng)態(tài)規(guī)劃方程：

??????當(dāng)求最大得分總和時(shí)

??????f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝

??????１≤k≤j－１

??????c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t

??????（２≤ｊ≤ｎ，１≤ｉ≤ｎ）

??????當(dāng)求最小得分總和時(shí)

??????f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝

??????１≤k≤j－１

??????c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t

??????（２≤ｊ≤ｎ，１≤ｉ≤ｎ）

??????其中x＝（i＋k－１）modn＋１，即第i堆數(shù)起，順時(shí)針數(shù)k＋１堆的堆序號(hào)。

??????例如對(duì)上面例子中的６(３ ４ ６ ５ ４ ２ )堆石子，按動(dòng)態(tài)規(guī)劃方程順推最小得分和。 依次得出含二堆石子的６個(gè)子序列的合并方案

??????f〔１，２〕＝７ f〔２，２〕＝１０ f〔３ ，２〕＝１１

??????c〔１，２〕＝１ c〔２，２〕＝１ c〔３，２〕＝１

??????f〔４，２〕＝９ f〔５，２〕＝６ f〔６，２〕＝５

??????c〔４，２〕＝１ c〔５， ２〕＝１ c〔６，２〕＝１

??????含三堆石子的６(３ ４ ６ ５ ４ ２ )個(gè)子序列的合并方案

??????f〔１，３〕＝２０ f〔２，３〕＝２５ f〔３，３〕＝２４

??????c〔１，３〕＝２ c〔２，３〕＝２ c〔３，３〕＝１

??????f〔４，３〕＝１７ f〔５，３〕＝１４ f〔６，３〕＝１４

??????c〔４，３〕＝１ c〔５，３〕＝１ c〔６，３〕＝２

??????含四堆石子的６(３ ４ ６ ５ ４ ２ )個(gè)子序列的合并方案

??????f〔１，４〕＝３６ f〔２，４〕＝３８ f〔３，４〕＝３４

??????c〔１，４〕＝２ c〔２，４〕＝２ c〔３，４〕＝１

??????f〔４，４〕＝２８ f〔５，４〕＝２６ f〔６，４〕＝２９

??????c〔４，４〕＝１ c〔５，４〕＝２ c〔６，４〕＝３

??????含五堆石子的６(３ ４ ６ ５ ４ ２ )個(gè)子序列的合并方案

??????f〔１，５〕＝５１ f〔２，５〕＝４８ f〔３，５〕＝４５

??????c〔１，５〕＝３ c〔２，５〕＝２ c〔３，５〕＝２

??????f〔４，５〕＝４１ f〔５，５〕＝４３ f〔６，５〕＝４５

??????c〔４，５〕＝２ c〔５，５〕＝３ c〔６，５〕＝３

??????含六堆石子的６(３ ４ ６ ５ ４ ２ )個(gè)子序列的合并方案

??????f〔１，６〕＝６１ f〔２，６〕＝６２ f〔３，６〕＝６１

??????c〔１，６〕＝３ c〔２，６〕＝２ c〔３，６〕＝２

??????f〔４，６〕＝６１ f〔５，６〕＝６１ f〔６，６〕＝６２

??????c〔４，６〕＝３ c〔５，６〕＝４ c〔６，６〕＝３

??????f〔１，６〕是f〔１，６〕，ｆ〔２，６〕，……f〔６，６〕中的最小值，表明最小得分和是由序列〔１，６〕經(jīng)５次合并得出的。我們從這個(gè)序列出發(fā)，

??????按下述方法倒推合并過(guò)程：

??????由c〔１，６〕＝３可知，第５次合并的兩堆石子分別由子序列〔１，３〕和子序列〔４，3〕經(jīng)４次合并后得出。其中c〔１，３〕＝２可知由子序列〔１，３〕合并成的一堆石子是由子序列〔１，２〕和第三堆合并而來(lái)的。而c〔１，２〕＝１，以表明了子序列〔１，２〕的合并方案是第１堆合并第２堆。

??????由此倒推回去，得出第１，第２次合并的方案，每次合并得分

??????第一次合并 ３ ４ ６…… 　　　->７

??????第二次合并 ７ ６…… ?????????->１３

??????１３……

??????子序列〔１，３〕經(jīng)２次合并后合并成１堆， ２次合并的得分和＝７＋１３＝２０。

??????ｃ〔４，３〕＝１，可知由子序列〔４，３〕合并成的一堆石子是由第４堆和子序列〔５，

??????２〕合并而來(lái)的。而c〔５，２〕＝１，又表明了子序列〔５，２〕的合并方案是第５堆合并第６堆。由此倒推回去，得出第３、第４次合并的方案

??????每次合并得分：

???????第三次合并 ……５４ ２ ????->６

??????第四次合并 ……５ ６ ???????->１１

??????……１１

??????子序列〔４，３〕經(jīng)２次合并后合并成１堆，２次合并的得分和＝６＋１１＝１７。

??????第五次合并是將最后兩堆合并成１堆，該次合并的得分為２４。

??????顯然，上述５次合并的得分總和為最小

??????２０＋１７＋２４＝６１

??????上述倒推過(guò)程，可由一個(gè)print（〔子序列〕）的遞歸算法描述

??????procedure print （〔i，ｊ〕）

??????begin

??????if ｊ〈〉１ then ｛繼續(xù)倒推合并過(guò)程

??????begin

??????print（〔i，c〔i，j〕〕；｛倒推子序列１的合并過(guò)程｝

??????print（〔i＋c〔i，j〕－１〕mod n＋１，j－c〔i，j〕）

??????｛倒推子序列２的合并過(guò)程｝

??????for K：＝１ to N do｛輸出當(dāng)前被合并的兩堆石子｝

??????if （第K堆石子未從圈內(nèi)去除）

??????then begin

??????if（K＝i）or（K＝X）then置第K堆石子待合并標(biāo)志

??????else第K堆石子未被合并；

??????end；｛then｝

??????第i堆石子數(shù)←第i堆石子數(shù)＋第X堆石子數(shù)；

??????將第X堆石子從圈內(nèi)去除；

??????end；｛then｝

??????end；｛print｝

??????例如，調(diào)用print（〔１，６〕）后的結(jié)果如下：

???????????????????????????print（〔１，６〕）⑤

????????????????????????????????┌──────┴──────┐

?????????????????????print（〔１，３〕）② ??????????????print（〔４，３〕）④

????????????????┌─────┴─────┐ ??????????????┌─────┴─────┐

??????????print(〔１，２〕)① print(〔3，1〕) ????print(〔4，1〕) print(〔５，２〕)③

???????┌──────┴──────┐ ????????????????????????┌──────┴──────┐ ?????????????

??????print（〔1,1〕） ???????print（〔2,1〕） ??????????????print（〔5,1〕） ????????

??????print（〔6,1〕）

??????（圖6.2-5）

??????其中回溯至

??????① 顯示 ３ ４６ ５ ４

??????② 顯示 ７ ６５ ４ ２

??????③ 顯示 １３ ５４ ２

??????④ 顯示 １３５ ６

??????⑤ 顯示 １３ １１

??????注:調(diào)用print過(guò)程后，應(yīng)顯示６堆石子的總數(shù)作為第５次合并的得分。

??????Program Stones;

??????Type

??????Node = Record{當(dāng)前序列的合并方案}

??????c : Longint;{得分和}

??????d : Byte{子序列1的堆數(shù)}

??????End;

??????SumType = Array [1..100,1..100] of Longint;

??????{sumtype[i,j]-子序列[i,j]的石子總數(shù)}

??????Var

??????List : Array [1..100,1..100] of Node;

??????{list[i,j]-子序列[i,j]的合并方案}

??????Date, Dt : Array [1..100] of Integer;

??????{Date[i]-第i堆石子數(shù),Dt-暫存Date}

??????Sum : ^SumType;{sum^[i,j]-指向子序列[i,j]的石子總數(shù)的指針}

??????F : Text;{文件變量}

??????Fn : String;{文件名串}

??????N, i, j : Integer;{N-石子堆數(shù),i,j-循環(huán)變量}

??????Procedure Print(i, j : Byte);{遞歸打印子序列[i,j]的合并過(guò)程}

??????Var

??????k, x : Shortint;{k-循環(huán)變量;x-子序列2中首堆石子的序號(hào)}

??????Begin

??????If j <> 1 Then Begin{繼續(xù)倒推合并過(guò)程}

????????Print(i, List[i,j].d);{倒推子序列1的合并過(guò)程}

????????x := (i + List[i, j].d - 1) Mod N + 1;{求子序列2中首堆石子的序號(hào)}

????????Print(x, j - List[i, j].d);{倒推子序列2的合并過(guò)程}

????????For k := 1 to N Do{輸出當(dāng)前合并第i堆,第x堆石子的方案}

??????????If Date[k] > 0 Then Begin

?????????????If (i= k)or(x=k)Then Write(F, - Date[k], ' ')

?????????????Else Write(F, Date[k], ' ')

??????????End; { Then }

????????Writeln(F);{輸出換行符}

????????Date[i] := Date[i] + Date[x];{原第i堆和第x堆合并成第ｉ堆}

????????Date[x] := - Date[x]{將原第x堆從圈內(nèi)去除}

????????End { Then }

??????End; { Print }

??????Procedure Main(s : Shortint);

??????Var

????????i, j, k : Integer;

????????t, x : Longint;

??????Begin

????????For i := 1 to N Do Begin{僅含一堆石子的序列不存在合并}

??????????List[i, 1].c := 0;

??????????List[i, 1].d := 0

????????End; {For}

????????For j := 2 to N Do{順推含2堆,含3堆……含N堆石子的各子序列的合并方案}

??????????For i := 1 to N Do Begin{當(dāng)前考慮從第i堆數(shù)起,順時(shí)針數(shù)j堆的子序列}

????????????If s = 1 Then List[i, j].c := Maxlongint{合并[i,j]子序列的得分和初始化}

?????????????Else List[i, j].c := 0;

????????????t := Sum^[i, j];{最后一次合并的得分為[i,j]子序列的石子總數(shù)}

????????????For k := 1 to j - 1 Do Begin{子序列1的石子堆數(shù)依次考慮1堆……j-1堆}

??????????????x := (i + k - 1) Mod N + 1;{求子序列2首堆序號(hào)}

??????????????If (s=1) And (List[i,k].c + List[x,j-k].c+t < List[i, j].c)

??????Or (s=2) And (List[i,k].c + List[x,j-k].c+t > List[i, j].c)

??????{ 若該合并方案為目前最佳,則記下}

??????????????Then Begin

????????????????List[i, j].c := List[i, k].c + List[x, j - k].c + t;

????????????????List[i, j].d := k

??????????????End { Then }

????????????End { For }

????????End; { For }

??????{在子序列[1,N],[2,N],……,[N, N]中選擇得分總和最小(或最大)的一個(gè)子序列}

????????k := 1; x := List[1, N].c;

????????For i := 2 to N Do

??????????If (s = 1) And (List[i, N].c < x) Or (s = 2) And

??????(List[i, N].c > x) Then Begin

?????????????k := i; x := List[i, N].c

??????????End; { Then }

????????Print(k, N);{由此出發(fā),倒推合并過(guò)程}

????????Writeln(F, Sum^[1, N]);{輸出最后一次將石子合并成一堆的石子總數(shù)}

????????Writeln(F);

????????Writeln(list[k, N].c)

??????End; { Main }

??????Begin

????????Write('File name = ');{輸入文件名串}

????????Readln(Fn);

????????Assign(F, Fn);{該文件名串與文件變量連接}

????????Reset(F);{文件讀準(zhǔn)備}

????????Readln(F, N);{讀入石子堆數(shù)}

????????For i := 1 to N Do Read(F, Date[i]);{讀入每堆石子數(shù)}

????????New(Sum);{求每一個(gè)子序列的石子數(shù)sum}

????????For i := 1 to N Do Sum^[i, 1] := Date[i];

????????For j := 2 to N Do

??????????For i := 1 to N Do

????????????Sum^[i, j] := Date[i] + Sum^[i Mod N + 1, j - 1];

????????Dt := Date;{暫存合并前的各堆石子,結(jié)構(gòu)相同的變量可相互賦值}

????????Close(F);{關(guān)閉輸入文件}

????????Assign(F, 'OUTPUT.TXT');{文件變量與輸出文件名串連接}

????????Rewrite(F);{文件寫準(zhǔn)備}

????????Main(1);{求得分和最小的合并方案}

????????Date := Dt;{恢復(fù)合并前的各堆石子}

????????Main(2);{求得分和最大的合并方案}

????????Close(F){關(guān)閉輸出文件}