问题1739--DP

1739: DP

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

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

输入

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

输出

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

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