5792 - 乘法游戏
时间限制 : 1 秒
内存限制 : 256 MB
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第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。
输入
第1行1个整数n，表示牌数。
第2行包括n个1~100的整数，每两个数之间用一个空格分开。
输出
一行一个整数，表示最小得分。
样例
输入
6 10 1 50 50 20 5
输出
3650
提示
【数据规模】
对于30%的数据满足：2≤n≤5。
对于60%的数据满足：2≤n≤20。
对于100%的数据满足：2≤n≤100。
来源
课课通