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

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=2000;
var n:longint;
    a:array[0..maxn] of longint;
    f,k:array[1..maxn,1..maxn] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     a[0]:=0;
     for i:=1 to n do
     begin
          readln(t);
          a[i]:=a[i-1]+t;
     end;
     close(input);
end;

function min(x,y:longint):longint;
begin
     if x>y then min:=y else min:=x;
end;

procedure pr;
var i,j,l,t,u:longint;
begin
     for i:=1 to n do k[i,i]:=i;
     for l:=2 to n do
         for i:=1 to n-l+1 do
         begin
              j:=i+l-1;
              for t:=k[i,j-1] to k[i+1,j] do
              begin
                   if t=i then continue;
                   u:=min(f[i,t-1]+a[t-1]-a[i-1],f[t,j]+a[j]-a[t-1]);
                   if u>f[i,j] then
                   begin
                        f[i,j]:=u;
                        k[i,j]:=t;
                   end;
              end;
         end;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(f[1,n]);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download