J18 习题-1 乘法游戏

题目描述

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第 $1$ 张和最后 $1$ 张牌。最后一次移动后，这里只剩下两张牌。 你的目标是使得分的和最小。 例如，如果数是 $10$、 $1$、 $50$ 、 $20$、 $5$，依次拿 $1$、 $20$、 $50$，总分是$10*1*50+50*20*5+10*50*5=8000$ 而拿 $50$、 $20$、$1$，总分是 $1*50*20+1*20*5+10*1*5=1150$。

输入格式

第一行包括牌数 $n$，第二行包括 $n$ 个 $1 \sim 100$ 的整数，用空格分开。

输出格式

输出文件只有一个数字：最小得分。

样例输入

6
10 1 50 50 20 5

样例输出

3650

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$3 \le n \le 100$。