「CODEVS1710」生日蛋糕
题目描述 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 Description
有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。
输出描述 Output Description
仅一行，是一个正整数S（若无解则S=0）。
样例输入 Sample Input
100
2
样例输出 Sample Output
68
数据范围及提示 Data Size & Hint
体积V=πR2H
侧面积A’=2πRH
底面积A=πR2
题解
搜索+剪枝
|
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 |
#include<iostream> #include<cstdio> #define inf 0x7fffffff using namespace std; int n,m,ans=inf; void dfs(int k,int r,int h,int s,int v) { if(v+m-k>n)return; if(v+(h-1)*(r-1)*(r-1)*(m-k)<n)return; if(2*(n-v)/r+s>=ans)return; if(k==m) { if(v==n)ans=s; return; } for(int i=m-k;i<=r-1;i++) for(int j=m-k;j<=h-1;j++) { if(s+2*i*j>=ans)break; dfs(k+1,i,j,s+2*i*j,v+i*i*j); } } int main() { scanf("%d%d",&n,&m); for(int i=m;i*i<=n;i++) for(int j=m;i*i*j<=n;j++) dfs(1,i,j,2*i*j+i*i,i*i*j); if(ans==inf)printf("0"); else printf("%d",ans); return 0; } |
Subscribe
计数器 9854623
OI 课件=>
OI 课件=>