ac1198.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1198;
const
  maxn=10000;
  maxm=20;
var
  minv,mins:array[0..maxm]of longint;
  n,m,best:longint;
procedure search(l,v,h,r,s:longint);
  var
    maxh,h1,r1,s1,i,maxv:longint;
  begin
    if l=0 then begin
      if (v=0) and (s<best) then best:=s;
      exit;
    end;
    for r1:=r-1 downto l do begin
      if l=m then s:=r1*r1;
      maxh:=(v-minv[l-1]) div (r1*r1);if maxh>h-1 then maxh:=h-1;
      for h1:=maxh downto l do begin
        s1:=s+2*r1*h1;
        if s1+mins[l-1]>=best then continue;
        maxv:=0;
        for i:=0 to l-1 do
          inc(maxv,sqr(r1-i)*(h1-i));
        if maxv<v then break;
        search(l-1,v-r1*r1*h1,h1,r1,s1);
      end;
    end;
  end;
begin
  for m:=1 to maxm do begin
    minv[m]:=minv[m-1]+m*m*m;
    mins[m]:=mins[m-1]+2*m*m;
  end;

  repeat
    read(n,m);
    best:=maxlongint;
    search(m,n,n+1,trunc(sqrt(n))+1,0);
    writeln(best);
  until seekeof;
end.