图a所示归并方式的总代价为：20+24+25+44+69+87=267 图b所示归并方式的总代价为：15+27+22+28+59+87=248 由此可见，不同的归并方式所得到的总代价是不一样的。那么当给出了n堆石子的数量之后，求出最小的总代价和最大的总代价。 Input
第一行一个整数 n，表示有 n 堆石子； 第二行有n个整数，表示每堆石子的个数； Output
第一行一个整数，表示合并的最小代价； 第二行一个整数，表示合并的最大代价； Sample Input 4
13 7 14 6 Sample Output
80 95 【算法分析】
（1）当N=2时，仅有一种堆法，因此总的归并代价为2堆沙子数量之和
（2）当N=3时，有2种堆法。从上图可看到它们总的代价分别为44和35。
（3）当N=4时，共有五种归并的方法，它们的总代价分别为94, 95, 80, 88, 87，最小的归并总代价为80（C）。
(A) (B) (C)
总代价=20+34+40=94 总代价=21+34+40=95 总代价=20+20+40=80
(D) (E)
总代价=21+27+40=88 总代价=20+27+40=8７
第一类包括（A），（B），基本方法是归并前面的三堆，再归并最后一堆，由于最后一堆归并的代价是相同的，所以在归并前面三堆时不同的方法将产生不同的结果。（A）的代价小于（B）的代价，因此（A）方法优。 第二类仅有一种方法（C），分别归并2堆的代价为２０，２０，相加为４０。 第三类包括（Ｄ），（Ｅ），基本方法是先归并后面三堆，再归并第一堆，由于最后一次归并代价是相同的，所以归并后三堆的方法不同将产生不同的结果。（Ｄ）的代价大于（Ｅ）的代价，因些方法（Ｅ）优。 引入数据结构：
1、F(i,j) 表示从i堆到j堆沙子归并的最小代价数。 如上讨论可知：
F(1,4)=MIN{ F(1,3), F(1,2)+F(3,4),F(2,4)}+40 而F(1,3)=min{F(1,2),F(2,3)}+34 F(1,2)=20 F(3,4)=20 F(2,3)=21
F(2,4)=MIN{F(2,3),F(3,4)}+27
2、g[i]：表示从第1堆到第i堆的石子的重量之和；
这样就有一般情况：
F(1,N)=MIN{ F(1,N-1), F(1,2)+F(3,N), F(1,3)+F(4,N), ……., F(2,N)}+G(N) G[i]：计算
for(i=1;i<=n;i++)g[i]=g[i-1]+a[i]; f[i][j]的计算过程：
如：
f(1,4)=min{f(1,3),f(1,2)+f(3,4),f(2,4)}+g(1,4) =min{43, 20+24, 46}+44 = 87
f(1,5)=min{f(1,4), f(1,2)+f(3,5),f(1,3)+f(4,5), f(2,5)}+g(1,5) =min{87 , 20+69, 43+37, 98}+65= 145 f(3,6)=min{f(3,5), f(3,4)+f(5,6),f(4,6)}+g(3,6)
=min{69, 24+25, 66}+49= 98
f(4,7)=min{f(4,6), f(4,5)+f(6,7),f(5,7)}+g(4,7)
=min{66, 37+22, 65}+59= 118
f(1,7)=min{f(1,6), f(1,2)+f(3,7), f(1,3)+f(4,7), f(1,4)+f(5,7), f(1,5)+f(6,7), f(2,7)}+g(1,7) =min{ 178, 20+156, 43+ 118, 87+ 65, 145+22, 185}+87=239 1、阶段和状态：设n堆石子的数量依次存储在a[1]、a[2]、?、a[n]中，由于本问题中只能是相邻两堆石子才能合并（与合并果子的区别），我们不妨设二维数组F，它的下标和值的含义分别为：
g[i]：表示从第1堆到第i堆的石子的重量之和；
fmin[i][j]:表示从第i堆到第j堆石子合并为一堆石子的最小代价; fmax[i][j]:表示从第i堆到第j堆石子合并为一堆石子的最大代价;
题目的阶段是：第几次合并t(1<=t<=n-1)，状态是：从第几堆开始合并石子i(1<=i<=n-t) 1、 状态转移方程：
f(1,n)=min{ f(1,n-1), f(1,2)+f(3,n), f(1,3)+f(4,n), ……., f(2,n)}+g(1,n) 初始化： g[i]=g[i-1]+a[i];fmax[i][i]=0; fmin[i][i]=0;
状态转移方程：fmin[i][j]=min{f[i][k]+f[k+1][j]+g[j]-g[i-1]}(i<=k<=j-1) 状态转移方程：fmax[i][j]=max{f[i][k]+f[k+1][j]+g[j]-g[i-1]}(i<=k<=j-1) Answer= fmin[1][n]和fmax[1][n] 3、核心子程序： void dp() { for(i=1;i<=n;i++)//计算g[i]的值
{ g[i]=g[i-1]+a[i]; fmax[i][i]=0; fmin[i][i]=0;} for(t=1;t<=n-1;t++)//阶段，第几次合并 for(i=1;i<=n-t;i++)//状态，合并的起始堆 { j=i+t; //合并的结束堆 fmin[i][j]=0x7fffffff; fmax[i][j]=0;//初始化 for(k=i;k<=j-1;k++) //决策，分界点 { fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]); fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]); } fmin[i][j]=fmin[i][j]+g[j]-g[i-1]; fmax[i][j]=fmax[i][j]+g[j]-g[i-1]; } } 4、完整的程序： #include #include const int maxn=2005,MAX=~0u>>3; int f[maxn][maxn]={0},s[maxn][maxn]={0},sum[maxn]={0},a[maxn],n,i; void init() { cin>>n; for(i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } for(i=1;i<=n*2;i++)sum[i]=sum[i-1]+a[i]; } void dp() { int j,k,l,ans; for(i=1;i<=n*2;i++)s[i][i]=i; for( l=2;l<=n;l++) for( i=1;i<=2*n-l+1;i++ ) { j=i+l-1; f[i][j]=MAX; for( k=s[i][j-1];k<=s[i+1][j];k++)//四边形不等式 if(f[i][j]>f[i][k-1]+f[k][j]) { f[i][j]=f[i][k-1]+f[k][j]; s[i][j]=k; } f[i][j]+=sum[j]-sum[i-1]; } ans=MAX; for(i=1;i<=n;i++)if(f[i][i+n-1] for(i=1;i<=2*n-l+1;i++) { j=i+l-1; //最大只来源于两种情况：i+(i+1?j)或(i?j-1)+j if(f[i][j-1]>f[i+1][j])f[i][j]=f[i][j-1]+sum[j]-sum[i-1]; else f[i][j]=f[i+1][j]+sum[j]-sum[i-1]; } ans=0; for(i=1;i<=n;i++)if(f[i][i+n-1]>ans)ans=f[i][i+n-1]; cout< 【例题】添加括号1688 【题目背景】给定一个正整数序列a(1)，a(2)，...，a(n),(1<=n<=20)，不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。 例如：给出序列是4,1,2,3。 第一种添括号方法：((4+1)+(2+3))=((5)+(5))=(10) 有三个中间和是5,5,10,它们之和为：5+5+10=20 第二种添括号方法：(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10) 中间和是3,6,10,它们之和为19。 【问题描述】现在要添上n-1对括号，加法运算依括号顺序进行，得到n-1个中间和，求出使中间和之和最小的添括号方法。