描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
|
|
开始以为通过贪心算法可能很快解决问题，可是是行不通的。
首先我们可以把这么堆石子看成一列
我们假如5堆的石子，其中石子数分别为7，6，5，7，100
•按照贪心法，合并的过程如下：
每次合并得分
第一次合并 7 6 5 7 100 =11
第二次合并 7 11 7 100=18
第三次合并 18 7 100 =25
第四次合并 25 100 =125
总得分＝11＋18＋25+125＝179
每次合并得分
第一次合并 7 6 5 7 100 ->13
第二次合并 13 5 7 100->12
第三次合并 13 12 100 ->25
第四次合并 25 100 ->125
总得分＝13＋12＋25+125＝175
显然利用贪心来做是错误的，贪心算法在子过程中得出的解只是局部最优,而不能保证使得全局的值最优。
因此我们需要通过动态规划算法来求出最优解。
在此我们假设有n堆石子，一字排开，合并相邻两堆的石子，每合并两堆石子得到一个分数，最终合并后总分数最少的。
我们设m(i,j)定义为第i堆石子到第j堆石子合并后的最少总分数。a(i)为第i堆石子得石子数量。
当合并的石子堆为1堆时，很明显m(i,i)的分数为0;
当合并的石子堆为2堆时，m(i,i+1)的分数为a(i)+a(i+1);
当合并的石子堆为3堆时，m(i,i+2)的分数为MIN((m(i,i)+m(i+1,i+2)+sum(i,i+2)),(m(i,i+1)+m(i+2,i+2)+sum(i,i+2));
当合并的石子堆为4堆时......
类似题目：nyoj 737 石子合并 poj 石子归并
nyoj 737 AC代码：
1 #include<stdio.h> 2 #define N 210 3 int minn(int p[N],int n) 4 { 5 int m[N][N]; 6 for(int x=1;x<=n;x++) 7 for(int z=1;z<=n;z++) 8 { 9 m[x][z]=-1; 10 } 11 int min=0; 12 for(int g=1;g<=n;g++)m[g][g]=0; 13 for(int i=1;i<=n-1;i++) 14 { 15 int j=i+1; 16 m[i][j]=p[i]+p[j]; 17 } 18 for(int r=3;r<=n;r++) 19 for(int i=1;i<=n-r+1;i++) 20 { 21 int j=i+r-1; 22 int sum=0; 23 for(int b=i;b<=j;b++) 24 sum+=p[b]; 25 m[i][j]=m[i+1][j]+sum; 26 for(int k=i+1;k<j;k++) 27 { 28 int t=m[i][k]+m[k+1][j]+sum; 29 if(t<m[i][j]) 30 m[i][j]=t; 31 } 32 } 33 min=m[1][n]; 34 return min; 35 } 36 int main() 37 { 38 int stone[N]; 39 int min=0; 40 int n; 41 while(scanf("%d",&n)!=EOF) 42 { 43 for(int i=1;i<=n;i++) 44 scanf("%d",&stone[i]); 45 min=minn(stone,n); 46 printf("%d ",min); 47 } 48 return 1; 49 }
nyoj上的这道题，讲的就是一条线上的相对简单一点；
以下是详细的解读；代码实现如下：
1 #include<stdio.h> 2 #define N 100 3 /* 4 *求合并过程中 5 *最少合并堆数目 6 **/ 7 int MatrixChain_min(int p[N],int n) 8 { 9 //定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目 10 //此处赋值为-1 11 12 int m[N][N]; 13 for(int x=1;x<=n;x++) 14 for(int z=1;z<=n;z++) 15 { 16 m[x][z]=-1; 17 } 18 19 int min=0; 20 //当一个单独合并时，m[i][i]设为0，表示没有石子 21 for(int g = 1;g<=n;g++) m[g][g]=0; 22 //当相邻的两堆石子合并时，此时的m很容易可以看出是两者之和 23 for(int i=1;i<=n-1;i++) 24 { 25 int j=i+1; 26 m[i][j]=p[i]+p[j]; 27 } 28 29 //当相邻的3堆以及到最后的n堆时，执行以下循环 30 for(int r=3; r<=n;r++) 31 for(int i=1;i<=n-r+1;i++) 32 { 33 int j = i+r-1; //j总是距离i r-1的距离 34 int sum=0; 35 //当i到j堆石子合并时最后里面的石子数求和得sum 36 for(int b=i;b<=j;b++) 37 sum+=p[b]; 38 39 // 此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+sum结果，这是其中一种可能，不一定是最优 40 //要与下面的情况相比较，唉，太详细了 41 42 m[i][j] = m[i+1][j]+sum; 43 44 //除上面一种组合情况外的其他组合情况 45 for(int k=i+1;k<j;k++) 46 { 47 int t=m[i][k]+m[k+1][j]+sum; 48 if(t<m[i][j]) 49 m[i][j] = t; 50 } 51 } 52 //最终得到最优解 53 min=m[1][n]; 54 return min; 55 } 56 57 /* 58 *求合并过程中 59 *最多合并堆数目 60 **/ 61 62 int MatrixChain_max(int p[N],int n) 63 { 64 int m[N][N]; 65 for(int x=1;x<=n;x++) 66 for(int z=1;z<=n;z++) 67 { 68 m[x][z]=-1; 69 } 70 71 int max=0; 72 //一个独自组合时 73 for(int g = 1;g<=n;g++) m[g][g]=0; 74 //两个两两组合时 75 for(int i=1;i<=n-1;i++) 76 { 77 int j=i+1; 78 m[i][j]=p[i]+p[j]; 79 } 80 81 for(int r=3; r<=n;r++) 82 for(int i=1;i<=n-r+1;i++) 83 { 84 int j = i+r-1; 85 int sum=0; 86 for(int b=i;b<=j;b++) 87 sum+=p[b]; 88 m[i][j] = m[i+1][j]+sum; 89 90 for(int k=i+1;k<j;k++) 91 { 92 int t=m[i][k]+m[k+1][j]+sum; 93 if(t>m[i][j]) 94 m[i][j] = t; 95 96 } 97 } 98 99 max=m[1][n]; 100 return max; 101 } 102 int main() 103 { 104 int stone[N]; 105 int min=0; 106 int max=0; 107 int n; 108 scanf("%d",&n); 109 for(int i=1;i<=n;i++) 110 scanf("%d",&stone[i]); 111 112 min= MatrixChain_min(stone,n); 113 max= MatrixChain_max(stone,n); 114 115 //因为题目要求圆的原因，要把所有情况都要考虑到，总共有n种情况。 116 //如果只是一条线上的,则下面的不用考虑的，例如nyoj737 117 for(int j=1;j<=n-1;j++) 118 { 119 int min_cache=0; 120 int max_cache=0; 121 int cache= stone[1]; 122 for(int k=2;k<=n;k++) 123 { 124 stone[k-1]=stone[k]; 125 } 126 stone[n]=cache; 127 min_cache= MatrixChain_min(stone,n); 128 max_cache= MatrixChain_max(stone,n); 129 if(min_cache<min) 130 min=min_cache; 131 if(max_cache>max) 132 max=max_cache; 133 } 134 135 printf("%d ",min); 136 printf("%d ",max); 137 138 return 1; 139 140 }