1724: 石子合并问题

题目描述

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

输入

输入数据的第1行是正整数n，1≤n≤100，表示有n堆石子。第二行有 n个数，分别表示每堆石子的个数。

输出

输出数据有两行，第1行中的数是最小得分，第2行中的数是最大得分。

样例输入

4
4 4 5 9

样例输出

43
54

参考代码

#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("%dn",min_count);
        printf("%dn",max);
    return 0;
}

解析

暂无