ac1229.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 48 行

program tju1229;
const
  max=100;
var
  area:array[1..max,1..max]of real;
  best:array[boolean,1..max,1..max]of real;
  m0,n0,l,m,n,i,j,x,y:byte;
  k1,k2,b,t:real;
  b1,b2:boolean;
begin
  repeat
    read(k1,k2,m0,n0);
    if (max mod n0=0) and (n0 mod m0=0) then begin
      writeln(sqr(max div m0)*k1*m0+sqr(max div n0)*k2*n0:0:1);
      continue;
    end;

    for l:=1 to max do
      for n:=1 to n0 do
        if n>l then
          area[l,n]:=9e9
        else
          area[l,n]:=sqr(l)*k1+(sqr(l div n)*(n-l mod n)+sqr(l div n+1)*(l mod n))*k2;

    best[true]:=area;
    for m:=2 to m0 do begin
      b1:=odd(m);b2:=not b1;
      for l:=1 to max do
        for n:=1 to n0 do
          best[b1,l,n]:=9e9;
      for l:=m to max do
        for n:=m to n0 do begin
          y:=1;
          for i:=1 to l-m+1 do begin
            b:=9e9;
            for j:=y to n-m+1 do begin
              t:=best[b2,l-i,n-j]+area[i,j];
              if t>b then break;
              b:=t;x:=j;
            end;
            if b<best[b1,l,n] then best[b1,l,n]:=b;y:=x;
          end;
        end;
    end;
    writeln(best[odd(m0),max,n0]:0:1);
  until seekeof;
end.