// Problem: Slimes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_dp_n
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define p_b push_back
#define ft first
#define nd second
#define pii pair<int, int>
#define pll pair<long long, long long>
using namespace std;

typedef long long ll;

ll nums[114514], sum[114514], f[5005][5005];

int main()
{
	int n;
	cin >> n;
	// for (int i = 1; i <= n; i++)
		// for (int j = 1; j <= n; j++)
			// f[i][j] = 1145141919810;
	// for (int i = 1; i <= n; i++) f[i][i] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> nums[i];
		sum[i] = sum[i - 1] + nums[i];
	}
	for (int i = 2; i <= n; i++) //长度
		for (int j = 1; j + i - 1 <= n; j++)//左端点
		{
			f[j][j + i - 1] = 1145141919810;
			for (int k = j; k < j + i - 1; k++)
				f[j][j + i - 1] = min(f[j][j + i - 1], 
				f[j][k] + f[k + 1][j + i - 1] + sum[j + i - 1] - sum[j - 1]);
		}
	cout << f[1][n];	
	return 0;
}

交洛谷的石子合并弱化版AC，atc的wa