生日蛋糕
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
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. |
博主求生日蛋糕的测试数据,不胜感激
@ReRe:我这里现在没有,抱歉。
@ceeji:那能讲下这道题那个题库能提交呢?
虽然看到题解很开心。。。可是。。。LZ你的程序AC不能啊。。。