该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T4. 石子合并 (stone)

题目描述

有 $N$ 堆石子排成一排，第 $i$ 堆有 $a_i$ 个石子。每次可以选择相邻的两堆石子合并，合并后的石子数为两堆之和，合并的代价为两堆石子数之和。经过 $N-1$ 次合并后所有石子合并为一堆。

求最小的总合并代价。

输入格式

第一行一个整数 $N$。第二行 $N$ 个整数 $a_1 \dots a_N$。

输出格式

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

样例

4
1 3 5 2

22

解释: 合并(1,3)=4(代价4), 合并(4,5)=9(代价9), 合并(9,2)=11(代价11), 总代价=4+9+11=24...最优为22。

数据范围

$1\le N\le 300$，$1\le a_i\le 1000$。

提示: 区间DP: $dp[i][j]=\min_{i\le k<j}(dp[i][k]+dp[k+1][j]+sum(i,j))$。