问题描述

设有N堆沙子排成一排，其编号为1,2,3,…,N(N<=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆，这样经过N-1次归并后成为一堆。找出一种合理的归并方法，使总的代价最小。

【输入格式】

    输入由若干行组成，第一行有一个整数，n（1≤n≤100）；表示沙子堆数。第2至m+1行是每堆沙子的数量。 

【输出格式】

    一个整数，归并的最小代价。

【输入样例】

输入文件名：shizi.in

7
13
7
8
16
21
4
18

【输出样例】

输出文件名：shizi.out

239

令f[i,j]表示归并第i个数到第j数的最小代价,sum[i,j]表示第i个数到第j个数的和，这个可以事先计算出来。sum[i,j]可以在O(1)的时间内算出.

/*
*f[i,j]表示從第i個到第j個歸併的最小代價
*sum[i,j]表示第i個數到第j個數的總和
*邊界條件：f[i][i]=0
           sum[i][i]=stone[i][i]
*總和遞推公式：sum[i][j]=sum[i][j-1]+stone[j]
*狀態轉移方程：f[i,j]=min{f[i,k]+f[k+1][j]+sum[i][j]}(i<=k<=j-1)
*目標結果：f[1,n]
*/

#include <iostream>
using namespace std;
#define M 101
#define INF 1000000000
int n;         //石子的堆數
int f[M][M];   //f[i,j]表示從第i個到第j個歸併的最小代價
int sum[M][M]; //sum[i,j]表示第i個數到第j個數的總和
int stone[M];  //每堆石子合併的代價
int main()
{
    freopen("shizi.in","r",stdin);
    freopen("shizi.out","w",stdout);
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d",&stone[i]);

    for(i=1;i<=n;i++)
    {
        f[i][i]=0;
        sum[i][i]=stone[i];
        for(j=i+1;j<=n;j++)
            sum[i][j]=sum[i][j-1]+stone[j];
    }

    for(int len=2;len<=n;len++)//归并的石子长度
    {
        for(i=1;i<=n-len+1;i++)//i為起點，j為終點
        {
            j=i+len-1;
            f[i][j]=INF;   //合併代價初始為最大值
            for(k=i;k<=j-1;k++)
            {
                if(f[i][j]>f[i][k]+f[k+1][j]+sum[i][j])
                    f[i][j]=f[i][k]+f[k+1][j]+sum[i][j];
            }
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}