记录编号	161324	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	Yeehok	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2015-05-04 17:09:05	内存使用	0.15 MiB

#include <fstream>
#include <cstring>
#define MaxInt 2147483646

using namespace std;

int n, Sands[101], Cost[101][101], Dp[101][101];

int Min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    ifstream cin("shizi.in");
    ofstream cout("shizi.out");
    cin >> n;
    memset(Sands, 0, sizeof(Sands));
    memset(Cost, 0, sizeof(Cost));
    for (int i = 0; i < n; i++) cin >> Sands[i];
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            for (int k = i; k <= j; k++)
                Cost[i][j] += Sands[k];
    for (int t = 1; t < n; t++) {
        for (int i = 0; i < n; i++) {
            int j = i + t;
            Dp[i][j] = MaxInt;
            for (int k = i; k < j; k++) {
                Dp[i][j] = Min(Dp[i][k] + Dp[k + 1][j] + Cost[i][j], Dp[i][j]);
            }
        }
    }
    cout << Dp[0][n - 1] << endl;
    
    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cout<<Dp[i][j]<<' ';
        cout<<endl;
    }*/
    return (0);
}