乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不允许拿第1张和最后1张牌。最后一次移动后,这里只剩下两张牌。
你的目标是使得分的和最小。
例如,如果数是10 1 50 205,依次拿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。
输入格式 Input Format
输入文件的第一行包括牌数(3<=n<=100),第二行包括N个1-100的整数,用空格分开。
输出格式 Output Format
输出文件只有一个数字:最小得分
6
10 1 50 50 20 5
样例输出 Sample Output[复制数据]
3650
program Project1;
var
n,i,j,l,k:longint;
a:array[1..100]of longint;
f:array[0..100,0..100]of longint;
begin
read(n);
for i:= 1 to n do
read(a[i]);
for i:= 3 to n do
for j:=1 to n-i+1 do
begin
l:=j+i-1; f[j,l]:=maxint;
for k:= j+1 to l-1 do
if f[j,l]>f[j,k]+f[k,l]+a[j]*a[l]*a[k] then
f[j,l]:=f[j,k]+f[k,l]+a[j]*a[l]*a[k];
end;
write(f[1,n]);
read(i);
end.