算法设计：石子合并

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

void findsum(int uSum[],int n,int sum[][100])
{
    int i,r;
    for(i=0;i<n;i++) sum[i][i]=uSum[i];
    for(r=1;r<n;r++)
        for(i=0;i<n;i++)
            sum[i][(i+r)%n]=sum[i][(i+r-1)%n]+uSum[(i+r)%n];
}

void join(int uSum[],int n,int *min,int *max)
{
    int i,r,k,t,tMax[100][100],tMin[100][100],sum[100][100];
    //find the sum

    findsum(uSum,n,sum);
    //one piece

    for(i=0;i<n;i++) tMax[i][i]=tMin[i][i]=0;
    //two piece and more

    //r is the length,kis the breaking point

    for(r=1;r<n;r++)
        for(i=0;i<n;i++)
        {
            tMax[i][(i+r)%n]=tMax[i][i]+tMax[(i+1)%n][(i+r)%n]+sum[i][(i+r)%n];
            tMin[i][(i+r)%n]=tMin[i][i]+tMin[(i+1)%n][(i+r)%n]+sum[i][(i+r)%n];
            for(k=i+1;k<i+r;k++)
            {
                t=tMax[i][k%n]+tMax[(k+1)%n][(i+r)%n]+sum[i][(i+r)%n];
                if(t>tMax[i][(i+r)%n]) tMax[i][(i+r)%n]=t;
                t=tMin[i][k%n]+tMin[(k+1)%n][(i+r)%n]+sum[i][(i+r)%n];
                if(t<tMin[i][(i+r)%n]) tMin[i][(i+r)%n]=t;
            }
        }
    //find the max and the min

    *max=tMax[0][n-1];
    *min=tMin[0][n-1];
    for(i=1;i<n;i++)
    {
        if(tMax[i][(i+n-1)%n]>*max) *max=tMax[i][(i+n-1)%n];
        if(tMin[i][(i+n-1)%n]<*min) *min=tMin[i][(i+n-1)%n];
    }
}

void main()
{
    int n,uSum[100],i,min,max;
    //Enter the data

    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&uSum[i]);
    //call the solution funtion

    join(uSum,n,&min,&max);
    printf("%d\n%d",min,max);
}