生日蛋糕（cake）【问题描述】7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1Ri1且Hi>Hi1，Ri、Hi均为整数。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q=Sπ请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。【输入格式】输入最多10组数据，每组数据包含两个整数N和M。输入以一个0结尾。【输出格式】对于每组数据，输出一个整数S。【输入样例】1002100030【输出样例】68316【数据范围】N<100001,M<11除了在搜索的时候当面积和体积加上当前最小面积体积大于总体积时剪枝之外还能怎么剪纸？？希望用PASCAL语言我看C看的很头疼谢谢
1． 切到当前层时表面积比最小的面积大，可以剪枝；2． 如果剩下的体积，比可能切出的最小体积小，最大体积大，剪枝。其实这些就够了，但是还可以进一步优化：对于当前的Lefts（剩下的需加上的面积），有Lefts=∑（k=i 1 to m）2*Rk*hk>=∑（k=i 1 to m）2*Rk^2*hk/Ri=2/Ri*(N-T)=PT为已经是已经使用的体积，W为已经用的面积，S为当前最小的面积，如果P>=S-W那么可以剪枝。program cgb;<br/> var<br/> n,m,r,h,i:longint;<br/> opt:longint;<br/> minv:array[0..20]of longint;<br/> function min(a,b:longint):longint;<br/> begin<br/> if ab then max:=a else max:=b;<br/> end;<br/> function maxv(r,h,k:longint):longint;<br/> var i:longint;<br/> begin<br/> maxv:=0;<br/> for i:=1 to k do<br/> begin<br/> dec(r);dec(h);<br/> if (r0)or((k=1)and(v=0))then<br/> if (maxv(r,h,k-1)>=v)and(minv[k-1]<=v)and(s1<opt) then<br/> dfs(k-1,r,h,s1,v);<br/> end;<br/> end;<br/> end;<br/> begin<br/> repeat<br/> opt:=maxlongint;<br/> readln(n,m);<br/> r:=0;h:=0;minv[0]:=0;<br/> for i:=1 to m do<br/> begin<br/> inc(r);inc(h);<br/> minv[i]:=minv[i-1] r*r*h;<br/> end;<br/> for r:=trunc(sqrt(n div m)) downto m do<br/> for h:=n div (r*r) downto m do<br/> if 2*r*h r*r<opt then<br/> dfs(m-1,r,h,2*r*h r*r,n-r*r*h);<br/> writeln(opt);<br/> until seekeof;<br/> end.
![]()
搜索
