前三堆所构成的花费是由 三部分构成，1、第一二合并的花费；2、第一二合并的个数和；3：第三堆本身个数

衍生一下，前四堆合并花费也一样由三部分，1、第一二三合并的花费，2、第一二三合并的个数和；3、第四堆本身个数

这样就很明显了，把大问题分解成了小问题，而且大问题包含了小问题的解，大问题和小问题同质同解。完完全全满足dp的性质。

#include<stdio.h>
#include<string.h>
#define Ma_x 99999
#define Mi_x 0 
#define min(a,b) a<b?a:b 
#define max(a,b) a>b?a:b 
int n,w[200],dp[200][200],dq[200][200];//n表示堆数，w表示每队的数量，dp[i][j]表示从第i堆开始合并j堆（包括第i堆）后的最小花费 ,dq表示最大 

题目描述

在一个圆形操场的四周摆放着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

算法分析

竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面

的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小(最大)的相邻两堆合并，

形成新的一堆；接下来，在N－1堆中选得分最小(最大)的相邻两堆合并……，依次类推，

直至所有石子经N－1次合并后形成一堆。

例如有６堆石子，每堆石子数(从最上面一堆数起，顺时针数)依次为３ ４６ ５ ４ ２

要求选择一种合并石子的方案，使得做５次合并，得分的总和最小。

按照贪心法，合并的过程如下：

每次合并得分

第一次合并 ３ ４ ６ ５ ４ ２ ５

第二次合并 ５ ４ ６ ５ ４ ９

第三次合并 ９ ６ ５ ４ ９

第四次合并 ９ ６ ９ １５

第五次合并 １５ ９ ２４

２４

总得分＝５＋９＋９＋１５＋２４＝６２

但是当我们仔细琢磨后，可得出另一个合并石子的方案：

每次合并得分

第一次合并 ３ ４ ６ ５ ４ ２ ７

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

第三次合并 １３ ５ ４ ２ ６

第四次合并 １３ ５ ６ １１

第五次合并 １３ １１ ２４

２４

总得分＝７＋６＋１１＋１３＋２４＝６１

显然，后者比贪心法得出的合并方案更优。 题目中的示例故意造成一个贪心法解题的

假像，诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来， 我们先来明确一

个问题：

１．最佳合并过程符合最佳原理

使用贪心法至所以可能出错， 是因为每一次选择得分最小(最大)的相邻两堆合并，

不一定保证余下的合并过程能导致最优解。聪明的读者马上会想到一种理想的假设：如果N

－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后

的得分总和必然是最优的。

例如上例中第五次合并石子数分别为１３和１１的相邻两堆。 这两堆石头分别由最初

的第１，２，３堆(石头数分别为３，４，６)和第４，５，６堆(石头数分别为５，４，

２)经４次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2 次合并的得分

总和最优。为了实现这一目标，我们将第１个序列又一分为二：第１、２堆构成子序列１，

第３堆为子序列２。第一次合并子序列１中的两堆，得分７； 第二次再将之与子序列２的

一堆合并，得分１３。显然对于第１个子序列来说，这样的合并方案是最优的。同样，我

们将第２个子序列也一分为二；第４堆为子序列１，第５，６堆构成子序列２。第三次合

并子序列２中的２堆，得分６；第四次再将之与子序列１中的一堆合并，得分１３。显然

对于第二个子序列来说，这样的合并方案也是最优的。 由此得出一个结论──６堆石子经

过这样的５次合并后，得分的总和最小。

我们把每一次合并划分为阶段，当前阶段中计算出的得分和作为状态， 如何在前一次

合并的基础上定义一个能使目前得分总和最大的合并方案作为一次决策。很显然，某阶段

的状态给定后，则以后各阶段的决策不受这阶段以前各段状态的影响。 这种无后效性的性

质符最佳原理，因此可以用动态规划的算法求解。

２．动态规划的方向和初值的设定

采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。 这些石子堆子序

列包括：

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

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

堆、第２堆｝；

……

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

……、第N－１堆｝

为了便于运算，我们用〔i，j〕表示一个从第i堆数起，顺时针数j堆时的子序列

｛第i堆、第i＋１堆、……、第(i＋j－1)mod n堆｝

它的最佳合并方案包括两个信息：

①在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和；

②形成最佳得分和的子序列１和子序列２。由于两个子序列是相邻的， 因此只需记住

子序列１的堆数；

设

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

c〔i，j〕──将〔i，j〕一分为二，其中子序列１的堆数；

(１≤i≤N，１≤j≤N)

显然，对每一堆石子来说，它的

f〔i，１〕＝０ c〔i，１〕＝０ (１≤i≤N)

对于子序列〔i，j〕来说，若求最小得分总和，f〔i，j〕的初始值为∞； 若求最大得

分总和，f〔i，j〕的初始值为０。(１≤i≤N，２≤j≤N)。

规划的方向是顺推。先考虑含二堆石子的N个子序列(各子序列分别从第１堆、第２堆、

……、第N堆数起，顺时针数２堆)的合并方案

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

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

然后考虑含三堆石子的Ｎ个子序列(各子序列分别从第１堆、第２堆、……、第Ｎ堆

数起，顺时针数３堆)的合并方案

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

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

……

依次类推，直至考虑了含N堆石子的N个子序列(各子序列分别从第１堆、第２堆、 …

…、第N堆数起，顺时针数N堆)的合并方案

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

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

最后，在子序列〔１，N〕，〔２，N〕，……，〔N，N〕中，选择得分总和(f值)最

小(或最大)的一个子序列〔i，N〕(１≤i≤N)，由此出发倒推合并过程。

３．动态规划方程和倒推合并过程

对子序列〔i，j〕最后一次合并，其得分为第i堆数起，顺时针数j堆的石子总数t。被

合并的两堆石子是由子序列〔i，k〕和〔(i＋k－１)modn＋１，j－k〕(１≤k≤j－１)

经有限次合并形成的。为了求出最佳合并方案中的k值，我们定义一个动态规划方程：

当求最大得分总和时

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

(２≤ｊ≤ｎ，１≤ｉ≤ｎ)

当求最小得分总和时

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堆数起，顺时针数k＋１堆的堆序号。

例如对(图6．2－4)中的６堆石子，按动态规划方程顺推最小得分和。 依次得出含

二堆石子的６个子序列的合并方案

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

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

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

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

含三堆石子的６个子序列的合并方案

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

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

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

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

含四堆石子的６个子序列的合并方案

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

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

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

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

含五堆石子的６个子序列的合并方案

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

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

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

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

含六堆石子的６个子序列的合并方案

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

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

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

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

f〔１，６〕是f〔１，６〕，ｆ〔２，６〕，……f〔６，６〕中的最小值，表明最小

得分和是由序列〔１，６〕经５次合并得出的。我们从这个序列出发， 按下述方法倒推合

并过程：

由c〔１，６〕＝３可知，第５次合并的两堆石子分别由子序列〔１，３〕和子序列〔

４，３〕经４次合并后得出。其中

c〔１，３〕＝２可知由子序列〔１，３〕合并成的一堆石子是由子序列〔１，２〕和

第三堆合并而来的。而c〔１，２〕＝１，以表明了子序列〔１，２〕的合并方案是第１堆

合并第２堆。

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

每次合并得分

第一次合并 ３ ４ ６…… ７

第二次合并 ７ ６…… １３

１３……

子序列〔１，３〕经２次合并后合并成１堆， ２次合并的得分和＝７＋１３＝２０。

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

２〕合并而来的。而c〔５，２〕＝１，又表明了子序列〔５，２〕的合并方案是第５堆合

并第６堆。由此倒推回去，得出第３、第４次合并的方案

每次合并得分

第三次合并 ……５４ ２ ６

第四次合并 ……５ ６ １１

……１１

子序列〔４，３〕经２次合并后合并成１堆，２次合并的得分和＝６＋１１＝１７。

第五次合并是将最后两堆合并成１堆，该次合并的得分为２４。

显然，上述５次合并的得分总和为最小

２０＋１７＋２４＝６１

上述倒推过程，可由一个print(〔子序列〕)的递归算法描述

procedure print (〔i，ｊ〕)

begin

if ｊ〈〉１ then ｛继续倒推合并过程

begin

print(〔i，c〔i，j〕)；｛倒推子序列１的合并过程｝

print(〔i＋c〔i，j〕－１)mod n＋１，j－c〔i，j〕)

｛倒推子序列２的合并过程｝

for K：＝１ to N do｛输出当前被合并的两堆石子｝

if (第K堆石子未从圈内去除)

then begin

if(K＝i)or(K＝X)then置第K堆石子待合并标志

else第K堆石子未被合并；

end；｛then｝

第i堆石子数←第i堆石子数＋第X堆石子数；

将第X堆石子从圈内去除；

end；｛then｝

end；｛print｝

例如，调用print(〔１，６〕)后的结果如下：

print(〔１，６〕)⑤

│

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

│ │

print(〔１，３〕)② print(〔４，３〕)④

│ │

print(〔１，２〕)① ┌─────┴─────┐

│ │ │

│

┌─────┴─────┐ print(〔４，１〕) print(〔５，２〕)③

│ │ │

print(〔１，１〕) print(〔２，１〕) │

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

│ │

print(〔５，１〕) print(〔６，１〕)

(图6.2-5)

其中回溯至

① 显示 ３ ４６ ５ ４

② 显示 ７ ６５ ４ ２

③ 显示 １３ ５４ ２

④ 显示 １３５ ６

⑤ 显示 １３ １１

注:调用print过程后，应显示６堆石子的总数作为第５次合并的得分。

代码：【c语言】

#include

#include

#include

#define max 100

int a[max],m[max][max],f[max][max];

int n;

FILE *fp;

int add(int x)

{

if(x!=n)

return ++x;

return 1;

}

int see(int x)

{

if(x%n==0)

return

n;

return (x%n);

}

void input()

{

int i,j,k,temp=0;

fp=fopen("input.txt","r");

if(fp==NULL)

exit(0);

fscanf(fp,"%d",&n);

for(i=1;i<=n;i++)

fscanf(fp,"%d",&a[i]);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

k=i;

while(k!=j)

{

temp+=a[k];

k=add(k); }

temp+=a[k];

m[i][j]=temp;

temp=0;

}

fclose(fp);

}

int fun(int i,int j)

{

if(i==j)

return

0;

if(see(i+1)==j)

return

m[i][j];

int min,k,temp;

k=i;

while(k!=j)

{

if(k==i)

{

min=f[i][k]+f[add(k)][j]+m[i][k]+m[add(k)][j];

k=add(k);

continue; }

temp=f[i][k]+f[add(k)][j]+m[i][k]+m[add(k)][j];

if(temp

min=temp;

k=add(k);

}

return min;

}

main()

{

input();

int i,j,min,temp,t;

for(temp=1;temp<=n;temp++)

for(i=1,j=temp;i<=n;i++)

{

f[i][see(j)]=fun(i,see(j));

j=add(j);

}

min=f[1][n];

for(i=2;i<=n;i++)

{

if(f[i][i-1]

min=f[i][i-1];

}

printf("%d",min);

getch();

}