設(shè)有N堆沙子排成一排，其編號(hào)為1，2，3，…，N（N< =300）。每堆沙子有一定的數(shù)量，可以用一個(gè)整數(shù)來描述，現(xiàn)在要將這N堆沙子合并成為一堆，每次只能合并相鄰的兩堆，合并的代價(jià)為這兩堆沙子的數(shù)量之和，合并后與這兩堆沙子相鄰的沙子將和新堆相鄰，合并時(shí)由于選擇的順序不同，合并的總代價(jià)也不相同，如有4堆沙子分別為 1 3 5 2 我們可以先合并1、2堆，代價(jià)為4，得到4 5 2 又合并 1，2堆，代價(jià)為9，得到9 2 ，再合并得到11，總代價(jià)為4+9+11=24，如果第二步是先合并2，3堆，則代價(jià)為7，得到4 7，最后一次合并代價(jià)為11，總代價(jià)為4+7+11=22；

問題是：找出一種合理的方法，使總的代價(jià)最小。輸出最小代價(jià)。

輸入格式：

第一行一個(gè)數(shù)N表示沙子的堆數(shù)N。 第二行N個(gè)數(shù)，表示每堆沙子的質(zhì)量。 < =1000

輸出格式：

合并的最小代價(jià)

樣例輸入

4
1 3 5 2
樣例輸出

22

#include<iostream>
using namespace std;
int a[1005];
int sum[1005];
int dp[1005][1005];
int main()
{
    int n;
    cin>>n;
    sum[0]=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum[i+1]=sum[i]+a[i];
    }
    for(int l=2;l<=n;l++)
        for(int i=1;i<=n-l+1;i++)
        {
            int j=i+l-1;
            dp[i][j]=9999999;
            for(int k=i;k+1<=j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);  //動(dòng)態(tài)規(guī)劃主要方程式
        }
    cout<<dp[1][n];
    return 0;
}