#1 waiting~@2012-03-19 04:39:00
25294
回复
删除
program xianglian(input,output);
const
maxn=100000;
var
p:array[1..100000] of longint;
f:array[0..10000,0..10000] of longint;
n,ans,i,j,k,l:longint;
begin
readln(n);
for i:=1 to n do
begin
read(p[i]);
p[i+n]:=p[i];
end;
for l:=1 to n-1 do
for i:=1 to 2*n-1 do
begin
j:=i+l;
if j>2*n-1 then
break;
for k:=i to j-1 do
if f[i,j]<f[i,k]+f[k+1,j]+p[i]*p[k+1]*p[j+1] then
f[i,j]:=f[i,k]+f[k+1,j]+p[i]*p[k+1]*p[j+1];
end;
for i:=1 to n do
if f[i,i+n-1]>ans then
ans:=f[i,i+n-1];
writeln(ans);
end.