问题1739--DP

1739: DP

时间限制: 1Sec 内存限制:128 MB
提交:52 解决:21
[ 状态] [ 讨论版] [ 提交] [命题人: ]
题目描述

给你n张卡牌。
开始时玩家得分为0,如果取走一张卡牌那么这张卡牌会消失,同是玩家将得到一定的分数,这个分数等于,这张卡牌和左右两张卡牌相乘的积。
如 1 2 3 4 5。这5张卡牌,取走2,玩家的到的分数为 1*2*3,卡牌变成 1 3 4 5.如果再取走3,那么玩家又会得到 1*3*4,的分数,
取走卡牌的顺序不限,并且第一张和最后一张不取。问你能得到的最小的分数是多少?

输入

多实例
第一行包含一个正整数 n(2接下来有n个小于100的正整数分别为1……n张卡牌的值。

输出

输出能得到的最小的分数值。

样例输入 Copy
3 1 2 3
样例输出 Copy
6
来源/分类