首页 > 代码库 > NOI1999 生日蛋糕
NOI1999 生日蛋糕
https://www.luogu.org/problem/show?pid=1731
题目背景
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<=20000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=15)，表示蛋糕的层数为M。
输出格式：
仅一行，是一个正整数S（若无解则S=0）。
输入输出样例
输入样例#1：
1002
输出样例#1：
68
搜索，剪枝
前两个最优性剪枝比较好想
关键是第三个：2*(n-V)/R>=ans-S
这是一个将体积与表面积结合的可行性剪枝
因为这一题搜索涉及两个变量，单纯对每一个变量剪枝效果甚微
所以这个剪枝最强效！！
证明：
剩余表面积=2*Σ（ri*hi）
剩余体积= Σ （ri*ri*hi）
剩余表面积=剩余体积*2/ri>=剩余体积*2/当前r
（剩下的ri一定比当前的r小，如果只剩一层就是等于，所以上式是>=）
即剩余最小表面积=剩余体积*2/当前r
如果它+当面表面积>=ans return
#include<cmath>#include<cstdio>#include<algorithm> using namespace std;int n,m,ans=2e9;int rest_V[20],rest_S[20];void dfs(int now,int V,int S,int R,int H){ if(now>m) { if(V==n) ans=min(ans,S); return ; } if(S+rest_S[m-now+1]>=ans) return; if(V+rest_V[m-now+1]>n) return; if(2*(n-V)/R>=ans-S) return; for(int i=R-1;i>=m-now+1;i--) for(int j=H-1;j>=m-now+1;j--) if(V+i*i*j<=n) dfs(now+1,V+i*i*j,S+2*i*j+(now==1)*i*i,i,j); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { rest_V[i]=rest_V[i-1]+i*i*i; rest_S[i]=rest_S[i-1]+2*i*i; } dfs(1,0,0,sqrt(n),n); if(ans==2e9) ans=0; printf("%d",ans);}
NOI1999 生日蛋糕
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。