在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

计算出将Ｎ堆石子合并成一堆的最小得分。

第一行为一个正整数N (2≤Ｎ≤100)；

以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。

一个正整数，即最小得分。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include<deque>

#define inf 0x3f3f3f3f

using namespace std;

int a[];

int dp[][];

//dp[i][j]是把第i堆推到第j堆得最优值

int s[];

int main()

{

    int n;

    cin>>n;

    s[]=;

        memset(dp,inf,sizeof(dp));

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

        dp[i][i]=;

        s[i]=s[i-]+a[i];

    }

     for(int i = n; i>=; i--)//不能反过来，因为，要在已知后面dp[i][k]+dp[k+1][j]的情况下推得

        for(int j = i + ; j <= n; j++)

            for(int k = i; k <= j - ; k++)

                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+][j]+s[j]-s[i-]);

    cout<<dp[][n];

    return ;

}