题目描述
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不允许拿第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,表示牌数(3≤n≤100)。
第二行包括n个1-100的整数,每两个数之间用一个空格分开。
提示
【数据规模】
对于30%的数据满足:2≤n≤5。
对于60%的数据满足:2≤n≤20。
对于100%的数据满足:2≤n≤100。