题目描述

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

输入

输入包括多组测试数据，每组测试数据包括两行。

第1 行是正整数n，1<=n<=100，表示有n堆石子。
第2行有n个数，分别表示每堆石子的个数。

输出

对于每组输入数据，输出两行。

第1 行中的数是最小得分；第2 行中的数是最大得分。

#include 
#include 
using namespace std;
int r[1005],c[1005][1005],sum[1005],s[1005][1005],x[1005];
int ans;
__attribute__((optimize("O2")))
int min(int x,int y)
{
  return xy?x:y;
}
__attribute__((optimize("O2")))
int main()
{
// freopen("power.in", "r", stdin);
 //freopen("power.out", "w", stdout);
  int n;
  ans=10000000;
  scanf("%d",&n);
  for (int i=1;i<=n;i++)
  {
    scanf("%d",&x[i]);  
    r[i]=x[i];
    sum[i]=sum[i-1]+r[i];      
    r[i+n]=r[i];
  }
  for (int l=1;l<=n;l++)
  {
    for (int i=1;i<=n;i++)
    {
      c[i][i]=0;
      s[i][i]=i;
    }
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        c[i][j]=0;
    for (int d=1;d<=n-1;d++)
      for (int i=1;i<=n-d;i++)
      {
        int j;
        j=i+d;
        c[i][j]=1000000;
        int tmp=sum[j]-(i>0?sum[i-1]:0);
        for (int k=s[i][j-1];k<=s[i+1][j];k++)
        {
          if (c[i][j]>c[i][k]+c[k+1][j]+tmp)
          {
             c[i][j]=c[i][k]+c[k+1][j]+tmp;
             s[i][j]=k;
          }
        }
      } 
    ans=min(ans,c[1][n]);
    for (int i=1;i<=1000;i++)
    {   
      r[i]=r[i+1];
      sum[i]=sum[i-1]+r[i];
    }
  }
  printf("%d\n",ans);
  ans=-10000;
  for (int i=1;i<=n;i++)
  {
      r[i]=x[i];
      sum[i]=sum[i-1]+r[i];  
      r[i+n]=r[i];
  }
  for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
        c[i][j]=0;
  for (int l=1;l<=n;l++)
  {
    for (int i=1;i<=n;i++)
    {
      c[i][i]=0;
      s[i][i]=i;
    }
    for (int d=1;d<=n-1;d++)
      for (int i=1;i<=n-d;i++)
      {
        int j;
        j=i+d;
        c[i][j]=0;
        int tmp=sum[j]-(i>0?sum[i-1]:0);
        for (int k=i;k<=j;k++)
        {
          if (c[i][j]