记录编号	27627	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2011-09-27 21:37:16	内存使用	0.34 MiB

/*
*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>
#include <cstdio>
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;
}