2223: 宝典2第三章乘法游戏

【题目描述】乘法游戏（Puzzle.cpp/c/pas）zju 1602

无聊的邪狼天天和别人玩乘法游戏，久而久之，居然练成了一身出神入化的牌技，然后……，然后就没有然后了，因为没有人愿意再和他玩第二次了。

乘法游戏是用一个序列的牌来玩的，每张牌都包含一个正整数作为其分值。当玩家将一张牌从序列中取走时，记录下这张牌与它左右两边牌的分值三者的乘积，将该乘积加入总分。这意味着第一张牌和最后一张牌不可被取走。取到最后，只有两张牌被留在序列中。

比如，如果牌的序列为10，1，50，20，5。其中10和5是不可被移动的。

现在取走“1”这张牌，则它左右的两张牌“10”和“50”将被计算，即10×1×50；再取走“20”，则“50”和“5”将被记录，即50×20×5；再取走50，则“10”和“5”将被记录，即10×50×5。最后的得分为：

10×1×50 + 50×20×5 + 10×50×5 = 500+5000+2500 = 8000。

但用另一种方法，如先取走50，再取走20，再取走1，最后得分将为：1×50×20 + 1×20×5 + 10×1×5 = 1000+100+50 = 1150。

显然第二种方法要比前一种得到的总分要小。

我们的最终目标是找到一种取法使总分最小。

【输入格式】

共两行。

第1行，包括一个数字N(5 ≤N ≤ 15)，表示牌的张数。

第2行，包含N个数，代表每张牌的分值，范围是从1到100，中间以空格分开。

【输出格式】

一个整数，即最小总分。

【输入样例】

6

10 1 50 50 20 5

【输出样例】

3650