记录编号	79676	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	gungnir	是否通过	通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2013-11-06 08:58:15	内存使用	0.18 MiB

var  i,n,t:longint;
     value:array[-1..40,-1..40]of longint;
     root:array[-1..40,-1..40]of longint;

procedure preorder(l,r:longint);

begin
if l>r then exit;
write(root[l,r],' ');
preorder(l,root[l,r]-1);
preorder(root[l,r]+1,r);
end;

procedure main;
var i,j,k:longint;
begin
for j:=3 to n do
for i:=1 to n-j+1 do
begin
value[i,i+j-1]:=value[i,i]+value[i+1,i+j-1];
root[i,i+j-1]:=i;
for k:=2 to j-1 do
if value[i+k-1,i+k-1]+value[i,i+k-2]*value[i+k,i+j-1]>value[i,i+j-1]
then
begin
value[i,i+j-1]:=value[i+k-1,i+k-1]+value[i,i+k-2]*value[i+k,i+j-1];
root[i,i+j-1]:=i+k-1;
end;
if value[i+j-1,i+j-1]+value[i,i+j-2]>value[i,i+j-1]
then
begin
value[i,i+j-1]:=value[i+j-1,i+j-1]+value[i,i+j-2];
root[i,i+j-1]:=i+j-1;
end;
end;
end;



begin
assign(input,'jfecs.in');reset(input);
assign(output,'jfecs.out');rewrite(output);
fillchar(value,sizeof(value),0);
readln(n);
for i:=1 to n do
begin read(t); value[i,i]:=t; root[i,i]:=i; end;
for i:=1 to n-1 do
begin
value[i,i+1]:=value[i,i]+value[i+1,i+1];
root[i,i+1]:=i;
end;
main;
writeln(value[1,n]);
preorder(1,n);
close(input);close(output);
end.