DTGAME - Tiền bạc luôn là thứ quý giá

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$R+,Q+}
{$Mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       2011;

var
  f1,f2         :       text;
  f,g           :       array[1..MAXN,1..MAXN] of longint;
  s             :       array[0..MAXN] of longint;
  n             :       longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        begin
          read(f1,s[i]);
          inc(s[i],s[i-1]);
        end;
    end;

procedure solve;
    var
      i,j,x,k:longint;
    begin
      for i:=n downto 1 do
        begin
          g[i,i]:=i;
          for j:=i+1 to n do
            begin
              for k:=g[i,j-1] to g[i+1,j] do
                if (i<k) then
                  begin
                    x:=min(f[i,k-1]+s[k-1]-s[i-1],f[k][j]+s[j]-s[k-1]);
                    if x>f[i,j] then
                      begin
                        f[i,j]:=x;
                        g[i,j]:=k;
                      end;
                  end;
            end;
        end;
      writeln(f2,f[1,n]);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Download