轉(zhuǎn)帖
在一個(gè)圓形操場(chǎng)的四周擺放著n堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。 
 
 
假設(shè)有n堆石子需要合并,可以設(shè)計(jì)一個(gè)2*n-1個(gè)元素的數(shù)組來(lái)存儲(chǔ)每堆石子的個(gè)數(shù)。
分析最優(yōu)解的結(jié)構(gòu)：假設(shè)有石頭AiAi+1……Aj需要合并,簡(jiǎn)記為A[i,j].如果設(shè)最后一次合并發(fā)生在Ak與Ak+1之間(i<=k<j),則最后一個(gè)合并的得分為Ai……Aj堆石頭的個(gè)數(shù)的總和記為totalValue(i,j).(不管你最后一次合并發(fā)生在哪個(gè)位置,totalValue(i,j)的值都是一樣的)因此總的得分等于A[i,k]的得分加上A[k+1,j]的得分再加上totalValue(i,j).
可以假設(shè)計(jì)算A[0,n-1]的一個(gè)最優(yōu)次序所包含的計(jì)算子鏈A[0,k]和A[K+1,n-1]的次序也是最優(yōu)的.
 證明:
 假設(shè)存在一個(gè)比計(jì)算A[0,k]的次序得分更少的次序,則用此次序來(lái)替換原來(lái)計(jì)算A[0,k]的次序,那么此時(shí)計(jì)算A[0,n-1]次序的得分就會(huì)比最優(yōu)次序所得到的分?jǐn)?shù)更少,這與假設(shè)相矛盾;同理可證明:計(jì)算A[0,n-1]的一個(gè)最優(yōu)次序所包含的另一個(gè)計(jì)算子鏈A[k+1,n-1]的次序也是最優(yōu)的!

綜上所述,此題滿足最優(yōu)子結(jié)構(gòu)性質(zhì),因此可以用動(dòng)態(tài)規(guī)劃算法來(lái)求解.
建立遞歸關(guān)系
設(shè)m[i][j]表示A[i,j]的計(jì)算結(jié)果.
當(dāng)i=j時(shí),表示只有一堆石頭,不能合并,因此得分為零,所以m[i,j]=0;
當(dāng)i<j時(shí),可利用最優(yōu)子結(jié)構(gòu)性質(zhì)來(lái)計(jì)算m[i][j],
m[i,j]=m[i,k]+m[k+1,j]+totalValue(i,j)(i<=k<j)

可用矩陣連乘的最優(yōu)計(jì)算次序問(wèn)題來(lái)求解這題.可選用自頂向下的備忘錄算法或是自底向上的動(dòng)態(tài)規(guī)劃算法.

以下代碼使用動(dòng)態(tài)規(guī)劃算法:

void MatrixChain(int *p,int n,int **m,int flag) //矩陣連乘算法
{
for(int i=0;i<n;i++)
m[i][i]=0;
for(int r=2;r<n;r++)
for(int i=0;i<n-r+1;i++)
{
int j=i+r-1;
int temp=totalValue(i,j,p);
m[i][j]=m[i+1][j]+temp;
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+temp;
if(!flag) //求最小得分
{
 if(t<m[i][j])
 m[i][j]=t;
}
else //求最大得分
if(t>m[i][j])
m[i][j]=t;
}
}
}
MatrixChain(inputNum,2*n-1,m,0); //計(jì)算最小得分
int resultMin=m[0][n-1];
for(i=1;i<=n-1;i++)
if(resultMin>m[i][n-1+i])
resultMin=m[i][n-1+i];

MatrixChain(inputNum,2*n-1,m,1); //計(jì)算最大得分
int resultMax=m[0][n-1];
for(i=1;i<=n-1;i++)
if(resultMax<m[i][n-1+i])
resultMax=m[i][n-1+i]; 
 
 
 

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/lyflower/archive/2008/03/05/2150239.aspx

一．試題
      在一個(gè)園形操場(chǎng)的四周擺放N堆石子（N≤100），現(xiàn)要將石子有次序地合并成一堆。規(guī)定
      每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。
      編一程序，由文件讀入堆數(shù)N及每堆的石子數(shù)（≤２０），
      ①選擇一種合并石子的方案，使得做N－1次合并，得分的總和最小；
      ②選擇一種合并石子的方案，使得做N－1次合并，得分的總和最大。
      例如，所示的４堆石子，每堆石子數(shù)（從最上面的一堆數(shù)起，順時(shí)針數(shù)）依
      次為４５９４。則３次合并得分總和最小的方案：８＋１３＋２２＝４３
      得分最大的方案為：１４＋１８＋２２＝５４
      輸入數(shù)據(jù)：
      文件名由鍵盤(pán)輸入，該文件內(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);{文件寫(xiě)準(zhǔn)備}
        Main(1);{求得分和最小的合并方案}
        Date := Dt;{恢復(fù)合并前的各堆石子}
        Main(2);{求得分和最大的合并方案}
        Close(F){關(guān)閉輸出文件}

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/lyflower/archive/2008/03/05/2150251.aspx