记录编号	5115	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2008-10-24 20:59:18	内存使用	0.12 MiB

program tree;
var
  st,d:array [0..31] of byte;
  n,i:byte;
  dp,t:array [0..30,0..30] of dword;
procedure go(a,b:byte);
var
  i,ti:byte;
  tmp:dword;
begin
  if a>=b then begin
    if a>b then dp[a,b]:=1;
    if a=b then begin
      dp[a,b]:=d[a];
      t[a,b]:=a;
    end;
  end
  else begin
    for i:=a to b do begin
      if dp[a,i-1]=0 then go(a,i-1);
      if dp[i+1,b]=0 then go(i+1,b);
      tmp:=dp[a,i-1]*dp[i+1,b]+d[i];
      if tmp>dp[a,b] then begin
        dp[a,b]:=tmp;
        ti:=i;
      end;
    end;
    t[a,b]:=ti;
  end;
end;
procedure make(x,y:byte);
begin
  if t[x,y]<>0 then begin
    inc(st[0]);
    st[st[0]]:=t[x,y];
  end;
  if t[x,y]-1>=x then make(x,t[x,y]-1);
  if t[x,y]+1<=y then make(t[x,y]+1,y);
end;
begin
  fillchar (dp,sizeof(dp),0);
  assign (input,'jfecs.in');
  reset (input);
  readln (n);
  for i:=1 to n do read (d[i]);
  st[0]:=0;
  close (input);
  assign (output,'jfecs.out');
  rewrite (output);
  go(1,n);
  writeln (dp[1,n]);
  make(1,n);
  write (st[1]);
  for i:=2 to st[0] do write (' ',st[i]);
  writeln;
  close (output);
end.