[BPOJ-R4E]序列得分
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小 得到了一个序列 ,其中有 个元素,第 个元素表示为 。
定义一次操作为从序列中选出一个元素 (),则该次操作得分为 ,且该序列的总得分为对该序列进行的所有操作的得分总和。
小 想进行若干次操作,直至序列中剩下首尾两个数为止,他希望序列的总得分最小,请你帮他找出最小总得分。
输入格式
第一行包含一个整数 ,表示序列的长度。
第二行包含 个整数,表示序列 。
输出格式
一行,一个整数,表示 序列的最小总得分。
样例输入输出
5
10 1 50 20 5
1150
10
30 6 67 93 20 62 1 26 49 74
17033
说明/提示
【样例解释 #1】
其中包含一种最优方案为 $1150 = 1 \times 50 \times 20 + 1 \times 20 \times 5 + 10 \times 1 \times 5 = 1000 + 100 + 50$。
【数据范围】
对于 的数据,满足 ,。