生日蛋糕

Birthday Cake

Cake.{pas|bas|c}
Cake.exe
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外，以上所有数据皆为正整数）
输入
有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。
输出
仅一行，是一个正整数S（若无解则S=0）。
样例输入
100
2
样例输出
68
附：圆柱公式
体积V=πR2H
侧面积A’=2πRH
底面积A=πR2
搜索题。
但是,朴素的搜索面临大数据超时的危机-_-||
所以,剪枝是必要的:
  • 最优化剪枝
    • k层蛋糕的最小表面积可知(h,r都为整数)
    • 当前s可知
    • 那么,s+剩下层数最小表面积>=min最无需再往下搜了
  • 可行性剪枝
    • k层蛋糕的最小体积minv可知
    • k层蛋糕的最大体积maxv可知
    • 那么,剩下的体积v不在minv至maxv的范围内,即可停止搜索

最优化剪枝数据越大功力越强..^-^

于是便可以写出程序了.

下面是我的程序，并没有加所有的剪枝……不过AC足够了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

//NOI1999-3: CAKE 
//2009-1-23: BY Ceeji 
//Type     : Search 
program noi1999_3; 
var n,m,i,j,k,l,q,max:longint; 
    mint,mins:array[0..20]of longint; 
procedure gettijimin; 
var i,j:longint; 
begin 
     j:=0;   mint[1]:=0; mint[0]:=0; 
     for i:=1 to m-1 do 
     begin 
          inc(j,i*i*i); 
          mint[i+1]:=j; 
     end; 
end; 
procedure getsmin; 
var i,j:longint; 
begin 
     j:=0;   mins[1]:=0; mins[0]:=0; 
     for i:=1 to m-1 do 
     begin 
          inc(j,2*i*i); 
          mins[i+1]:=j; 
     end; 
end; 
procedure sou(i,v,s,h,r:longint); // i: ceng shu; v:ti ji; s:mian ji; h:max {height}; 
var j,k,l,q:longint; 
begin 
     if (i=m+1)and(v=0)and(max>s)then 
     begin 
          max:=s; exit; 
     end; 
     if (i>m)or(v< =0) then exit; 
     for j:=h downto m-i+1 do 
     begin 
         for q:=r downto m-i+1 do 
         begin 
              if (i=m)and(q*q*j<>v)then continue; 
              if s+2*q*j+mins[m-i+1]>=max then continue; 
              if i<>1 then sou(i+1,v-q*q*j,s+2*q*j,j-1,q-1) 
                      else sou(i+1,v-q*q*j,s+2*q*j+q*q,j-1,q-1); 
         end; 
     end; 
end; 
begin 
     readln(n,m); 
     max:=100000000; 
     gettijimin; getsmin; 
     k:=mint[m]; 
     if n-k< =0 then begin writeln('0'); exit; end; 
     sou(1,n,0,trunc((n-k)/(m*m)),trunc(sqrt((n-k)/m))); 
     if max=100000000 then writeln('0') else writeln(max); 
end.