ac1246.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

{$Q-,R-}
program tju1246;
const
  maxn=20;
var
  a,s:array[0..maxn]of word;
  cut,min:array[1..maxn,1..maxn]of word;
  n,i,j,k,t:longint;
procedure dfs1(l,r:byte);
  begin
    if l=r then
      write(a[l])
    else begin
      write('(');
      dfs1(l,cut[l,r]);
      write('+');
      dfs1(cut[l,r]+1,r);
      write(')');
    end;
  end;
procedure dfs2(l,r:byte);
  begin
    if l=r then exit;
    dfs2(l,cut[l,r]);
    dfs2(cut[l,r]+1,r);
    write(s[r]-s[l-1]);
    if (l>1) or (r<n) then write(' ') else writeln;
  end;
begin
  repeat
    read(n);
    for i:=1 to n do begin
      read(a[i]);s[i]:=s[i-1]+a[i];
    end;

    for i:=1 to n-1 do begin
      min[i,i+1]:=s[i+1]-s[i-1];
      cut[i,i+1]:=i;
    end;
    for k:=2 to n-1 do
      for i:=1 to n-k do begin
        min[i,i+k]:=maxint;
        for j:=cut[i+1,i+k] downto cut[i,i+k-1] do begin
          t:=min[i,j]+min[j+1,i+k];
          if t<min[i,i+k] then begin
            min[i,i+k]:=t;cut[i,i+k]:=j;
          end;
        end;
        inc(min[i,i+k],s[i+k]-s[i-1]);
      end;

    dfs1(1,n);writeln;
    writeln(min[1,n]);
    dfs2(1,n);
  until seekeof;
end.