石子合并

admin

【石子合并】
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最大得分。
【输入文件】
包含两行，第1 行是正整数n（1<=n<=100），表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。
【输出文件】
输出两行。
第1行中的数是最大得分。
【输入样例】
4
4 4 5 9
【输出样例】
54
[code=Cpp width=700px]
//f[j]表示从第i堆石子，开始取j堆。
//s[j]表示从i开始数j个石子堆的和
#include <stdio.h>
int main()
{
        int f[101][101]={0},s[101][101]={0},a[202];
        int i,j,k,n,t;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
                scanf("%d",&a);
                a[i+n]=a;
        }
        for(i=1;i<=n*2;i++)
                printf("%d ",a);

        for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                        for(k=i;k<=i+j-1;k++)
                        {
                                if(k>n) t=k%n;
                                else t=k;

                                s[j]=s[j]+a[t];
                        }

        for(j=2;j<=n;j++)
                for(i=1;i<=n;i++)
                        for(k=1;k<=j-1;k++)
                        {
                                t=i+k;
                                if(t>n) t=t%n;
                                if ( f[j] <  f[k]+f[t][j-k]+s[j] )
                                        f[j] = f[k]+f[t][j-k]+s[j];
                        }

        printf("\n\n");
        for(i=1;i<=n;i++)
        {
                for(j=1;j<=n;j++)
                {
                        printf("%d ",f[j]);
                }
                printf("\n");
        }


        sleep(500000);
        return 0;
}

[/code]