石子合并问题

石子合并问题

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注