p1100.pas

www.vijos.cn上一些习题的参考源码

program binary;
const
    MAXN=30;
var
    fin,fout:text;
    a:array[1..MAXN] of longint;
    f:array[0..MAXN,0..MAXN] of longint;
    root:array[0..MAXN,0..MAXN] of longint;
    n,i,j,d,k,t:longint;

procedure preorder(i,j:longint);
var
    k:longint;
begin
    if i>j then exit;
    k:=root[i,j];
    write(k,' ');
    preorder(i,k-1);
    preorder(k+1,j);
    
end;


begin
    readln(n);
    for i:=1 to n do
        read(a[i]);

    for i:=1 to n do begin
        f[i,i]:=a[i];
        root[i,i]:=i;
        f[i,i-1]:=1;
        f[i-1,i]:=1;
    end;

    for d:=1 to n-1 do begin
        for i:=1 to n-d do begin
            j:=i+d;
            for k:=i to j do begin
                t:=f[i,k-1]*f[k+1,j]+a[k];
                if t>f[i,j] then begin
                    f[i,j]:=t;
                    root[i,j]:=k;
                end;
            end;
        end;
    end;
    
    writeln(f[1,n]);
    preorder(1,n);
end.