306018 - 乘法游戏

题目描述】6.18 乘法游戏（Puzzle）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。最后的得分为： 1 0×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，中间以空格分开。

一个整数，即最小总分。