普及+/提高⏱ 1000ms💾 256MB#P6003

题目描述

$n$ 堆石子排成一排,每次可以把相邻两堆合并成一堆,代价是两堆石子数之和。合并 $n-1$ 次后只剩一堆。

输出最小总代价。

输入格式

第一行,一个整数 $n$

第二行,$n$ 个整数,表示每堆石子数。

输出格式

一行,一个整数,表示最小总代价。

数据范围

$$1 \le n \le 300,\ 1 \le x_i \le 10^4$$

样例输入 #1
4
4 1 5 2
样例输出 #1
24
样例输入 #2
3
1 2 3
样例输出 #2
9