题目描述

设有一排数，共n(n<=1000)，例如:22,14,7,13,26,15,11。任意两个数可以进行归并，归并的代价为该两个数的和，经过不断归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使代价总和最小。
例如三个数，12，7 ，8，归并的过程有2种。如下图：

由此可见，第二种归并的方法总代价为最小。

输入

第一行N，第二行N个数

输出

一个数，最小归并值

#include 
#include 
using namespace std;
int r[10100],c[5100][5010],sum[10010],s[1005][1005];
int ans=0xfffffff;
int min(int x,int y)
{
  return xmain()
{
  int n;
  scanf("%d",&n);
  for (int i=1;i<=n;i++)
  {
    scanf("%d",&r[i]);  
    sum[i]=sum[i-1]+r[i];      

  }
    for (int i=1;i<=n;i++)
    {
      c[i][i]=0;
      s[i][i]=i;
    }
    for (int d=1;d<=n;d++)
      for (int i=1;i<=n-d+1;i++)
      {
        int j;
        j=i+d;
        c[i][j]=0xfffffff;
        int tmp=sum[j]-(i==0?0:sum[i-1]);
        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;
            }
        }
      } 

  printf("%d\n",c[1][n]);
  return 0;
}