stock.cpp

在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆

#include"stdio.h"
#include"malloc.h"
//void array(int c[],int n){
	//int temp;
	//temp=c[0];
	//for(int i=0;i<n-1;i++)
	//	c[i]=c[i+1];
    //c[i]=temp;
//}
int Matrix(int c[],int n){
	int a[100][100],op[100][100];
	int i,j,r,temp,k;
	for(i=0;i<n;i++){
		a[i][i]=c[i];op[i][i]=0;
	}
	for(r=1;r<n;r++)
		for(i=0;i<n-r;i++){
			j=i+r;
			a[i][j]=a[i][j-1]+a[j][j];
			op[i][j]=a[i][j]+op[i][i]+op[i+1][j];
			for(k=i+1;k<j;k++){
				temp=a[i][j]+op[i][k]+op[k+1][j];
				if(temp<op[i][j])op[i][j]=temp;
			}
		}
    return op[0][n-1];
}
int Maxtrix(int c[],int n){
    int a[100][100],op[100][100];
	int i,j,r,temp,k;
	for(i=0;i<n;i++){
		a[i][i]=c[i];op[i][i]=0;
	}
	for(r=1;r<n;r++)
		for(i=0;i<n-r;i++){
			j=i+r;
			a[i][j]=a[i][j-1]+a[j][j];
			op[i][j]=a[i][j]+op[i][i]+op[i+1][j];
			for(k=i+1;k<j;k++){
				temp=a[i][j]+op[i][k]+op[k+1][j];
				if(temp>op[i][j])op[i][j]=temp;
			}
		}
    return op[0][n-1];
}
int main(){
	int i,n,temp,l;
	int *c,*min,*max;
	int big,little;
    scanf("%d",&n);
    c=(int *)malloc(sizeof(int)*n);
	min=(int *)malloc(sizeof(int)*n);
	max=(int *)malloc(sizeof(int)*n);
	for(i=0;i<n;i++)
	 scanf("%d",c+i);
	for(i=0;i<n;i++){
		min[i]=Matrix(c,n);
		max[i]=Maxtrix(c,n);
		temp=*c;
	    for(l=0;l<n-1;l++)
		  *(c+l)=*(c+l+1);
         *(c+l)=temp;
	}
	little=min[0];
	big=max[0];
	for(i=1;i<n;i++){
		if(*(min+i)<little)little=*(min+i);
		if(*(max+i)>big)big=*(max+i);
	}
	printf("%d\n",little);
	printf("%d",big);
}