石子合并问题
时间： 1ms 内存：64M
描述：
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
对于给定n堆石子,计算合并成一堆的最小得分和最大得分。
输入：
输入数据的第1行是正整数n，1≤n≤100，表示有n堆石子。第二行有 n个数，分别表示每堆石子的个数。
输出：
输出数据有两行，第1行中的数是最小得分，第2行中的数是最大得分。
示例输入：
4
4 4 5 9示例输出：
43
54提示：
参考答案（内存最优[800]）：
#include<stdio.h>
#define N 100
/*
*求合并过程中
*最少合并堆数目
**/
int MatrixChain_min(int p[N],int n)
{
//定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目
//此处赋值为-1
int m[N][N];
for(int x=1;x<=n;x++)
for(int z=1;z<=n;z++){
m[x][z]=-1;
}
int min=0;
//当一个单独合并时，m[i][i]设为0，表示没有石子
for(int g = 1;g<=n;g++) m[g][g]=0;
//当相邻的两堆石子合并时，此时的m很容易可以看出是两者之和
for(int i=1;i<=n-1;i++){
int j=i+1;
m[i][j]=p[i]+p[j];
}
//当相邻的3堆以及到最后的n堆时，执行以下循环
for(int r=3; r<=n;r++)
for(int i=1;i<=n-r+1;i++){
int j = i+r-1; //j总是距离i r-1的距离
int sum=0;
//当i到j堆石子合并时最后里面的石子数求和得sum
for(int b=i;b<=j;b++)
sum+=p[b];
// 此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+sum结果，这是其中一种可能，不一定是最优
//要与下面的情况相比较，唉，太详细了
m[i][j] = m[i+1][j]+sum;
//除上面一种组合情况外的其他组合情况
for(int k=i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+sum;
if(t<m[i][j])
m[i][j] = t;
}
}
//最终得到最优解
min=m[1][n];
return min;
}
/*
*求合并过程中
*最多合并堆数目
**/
int MatrixChain_max(int p[N],int n){
int m[N][N];
for(int x=1;x<=n;x++)
for(int z=1;z<=n;z++){
m[x][z]=-1;
}
int max=0;
//一个独自组合时
for(int g = 1;g<=n;g++) m[g][g]=0;
//两个两两组合时
for(int i=1;i<=n-1;i++){
int j=i+1;
m[i][j]=p[i]+p[j];
}
for(int r=3; r<=n;r++)
for(int i=1;i<=n-r+1;i++){
int j = i+r-1;
int sum=0;
for(int b=i;b<=j;b++)
sum+=p[b];
m[i][j] = m[i+1][j]+sum;
for(int k=i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+sum;
if(t>m[i][j])
m[i][j] = t;
}
}
max=m[1][n];
return max;
}
main() {
int stone[N];
int min=0;
int max=0;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&stone[i]);
min= MatrixChain_min(stone,n);
max= MatrixChain_max(stone,n);
//因为题目要求圆的原因，要把所有情况都要考虑到，总共有n种情况。
for(int j=1;j<=n-1;j++){
int min_cache=0;
int max_cache=0;
int cache= stone[1];
for(int k=2;k<=n;k++){
stone[k-1]=stone[k];
}
stone[n]=cache;
min_cache= MatrixChain_min(stone,n);
max_cache= MatrixChain_max(stone,n);
if(min_cache<min)
min=min_cache;
if(max_cache>max)
max=max_cache;
}
printf("%d\n",min);
printf("%d\n",max);
return 1;
}
参考答案（时间最优[4]）：
#include<stdio.h>
int N;//最多100堆石子:N=100
int num[200]={0};
int max=-0x3f3f3f3f;
int stone_merge()
{
int score[200][101]={0};//l[i][j]:从第i堆石子起合并n堆石子的最小得分
int score2[200][101]={0};
int n,i,k,temp,t2;
for(i=0;i<2*N;i++)
{
score[i][1]=0;//一堆石子合并得分为0
score2[i][1]=0;
}
for(n=2;n<=N;n++)//合并n堆石子
{
for(i=0;i<=2*N-n;i++)//从第i对开始合并(有一次重复运算，但省去了循环取数，简化了程序)
{
score[i][n]=score[i][1]+score[i+1][n-1];
score2[i][n]=score2[i][1]+score2[i+1][n-1];
for(k=2;k<n;k++)//划分
{ temp=score[i][k]+score[k+i][n-k];
t2=score2[i][k]+score2[k+i][n-k];
if(temp<score[i][n])
score[i][n]=temp;//取(i,n)划分两部分的得分
if(t2>score2[i][n])
score2[i][n]=t2;
}
for(k=i;k<i+n;k++)
{
score[i][n]+=num[k];//加上此次合并得分
score2[i][n]+=num[k];
}
}
}
int min=2147483647;//int(4位)最大值为2147483647
for(i=0;i<N;i++)
{
if(score[i][N]<min)
min=score[i][N];//从第i堆开始取N堆石子，的最小合并得分
if(score2[i][N]>max)
max=score2[i][N];
}
return min;
}
int main()
{
int min_count;
scanf("%d",&N);//N堆石子
for(int i=0;i<N;i++)
scanf("%d",&num[i]);//每堆石子的数量
for(int i=N;i<2*N;i++)
num[i]=num[i-N];//复制一倍，化简环形计算（N堆石子是围成一个环的）
if(N==1) min_count=0;
else if(N==2) min_count=num[0]+num[1];
else min_count=stone_merge();
printf("%d\n",min_count);
printf("%d\n",max);
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。