各位天才帮帮小女子我吧！ [复制链接]

生日蛋糕(NOI1999)

Time Limit:1000MS  Memory Limit:65536K

Description

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i＜M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。

令Q=Sπ,请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
(除Q外，以上所有数据皆为正整数）


Input

有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。

Output

仅一行，是一个正整数S（若无解则S=0）。

Sample Input


100
2


Sample Output


68









我是初三的女生，实在做不来，希望各位指导！谢谢各位哥哥姐姐了！

思路

      dfs.加最优化剪支,可行性剪支.

参考程序

var
  k,s,m,n,min,v,z3:longint;
  z1,z2:array[0..20] of longint;

procedure init;
  var
    i:longint;
  begin
    min:=maxlongint;
    z1[0]:=0;
    for i:=1 to m do
      z1:=z1[i-1]+i*i*i;
    z2[0]:=0;
    for i:=1 to m do
      z2:=z2[i-1]+2*i*i;
  end;

procedure search(r,h,k:longint);
  var
    i,j,th,tr,tk:longint;
  begin
    if k=m+1 then
      begin
        if (v=n) and (s<min) then min:=s;
        exit;
      end;

    if z1[m-k]+v>n then exit;
    if z2[m-k]+s>min then exit;
    z3:=0; tk:=m-k+1; th:=h; tr:=r;
    while tk>0 do
      begin
        z3:=z3+tr*tr*th;
        dec(tr); dec(th); dec(tk);
      end;
    if z3+v<n then exit;

    for i:=r-1 downto m-k+1 do
      for j:=h-1 downto m-k+1 do
        begin
          if k=1 then s:=i*i;
          s:=s+2*i*j;
          v:=v+i*i*j;
          if v<=n then search(i,j,k+1);
          s:=s-2*i*j;
          v:=v-i*i*j;
        end;
  end;


begin
  readln(n);
  readln(m);
  init;
  search(trunc(sqrt(n)),trunc(sqrt(n)),1);
  if min=maxlongint then min:=0;
  writeln(min);
end.
你才初3。。这种东西不适合你。先从简单的开始，时间会让一切都变得清晰，我到高三才明白

虽然我看不懂，不过还是谢谢你的好意啦！

如果你不介意我们可以交个朋友，
我的QQ号是：121371490
我们的信息学奥赛交流QQ群是：33498757

easy

i agree with you