POJ1190生日蛋糕[DFS 剪枝]

时间:2022-09-15 19:29:01
生日蛋糕
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 18236   Accepted: 6497

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

有两行,第一行为N(N <= 10000),表示待制作的蛋糕的体积为Nπ;第二行为M(M <= 20),表示蛋糕的层数为M。

Output

仅一行,是一个正整数S(若无解则S = 0)。

Sample Input

100
2

Sample Output

68

Hint

圆柱公式 
体积V = πR2
侧面积A' = 2πRH 
底面积A = πR2 

Source


一开始想的是从上往下搜,可以用A*的估价函数剪枝(因为下面的r和h都比上面的大)
然而题解都是递推了mnv[]和mns[]然后用他们从下往上搜
比较神的一个剪枝是2*(n-v)/lr+s>ans
2*(n-v)/lr这块是剩下的体积所能围成图形面积下限,因为推导一下可知圆柱v不变,侧面积与r成反比
还有h的范围,mxh=min(lh-1,(n-mnv[d-1]-v)/(tr*tr));
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=;
int n,m,ans=1e9;
int mnv[N],mns[N];
void init(){
for(int i=;i<=m;i++){
mnv[i]=mnv[i-]+i*i*i;
mns[i]=mns[i-]+*i*i;
}
}
void dfs(int d,int lh,int lr,int s,int v){
if(d==){
if(v==n&&s<ans) ans=s;
return;
}
if(v+mnv[d]>n||s+mns[d]>ans) return;
if(*(n-v)/lr+s>ans) return;
for(int tr=lr-;tr>=d;tr--){
if(d==m) s=tr*tr;
int mxh=min(lh-,(n-mnv[d-]-v)/(tr*tr));
for(int th=mxh;th>=d;th--){
dfs(d-,th,tr,s+*th*tr,v+tr*tr*th);
}
}
}
int main(){
scanf("%d%d",&n,&m);
init();
dfs(m,n-mnv[m-],sqrt(n-mnv[m-])+,,);
printf("%d",ans);
}
 
 

POJ1190生日蛋糕[DFS 剪枝]的更多相关文章

  1. poj1190 生日蛋糕 dfs

    题意:生日蛋糕有m层,总体积是V.从下向上,每一层的半径r和高度h都是递减的. 给m.v,求最小的表面积s.(不算底面接地的面积) 题目链接:poj1190 剪枝都还没加..样例输出都是错的...还没 ...

  2. &lbrack;洛谷P1731&rsqb;&lbrack;NOI1999&rsqb;生日蛋糕&lpar;dfs&rpar;&lpar;剪枝&rpar;

    典型的深搜+剪枝策略 我们采用可行性剪枝.上下界剪枝.优化搜索顺序剪枝.最优性剪枝的方面来帮助我们进行剪枝. 也许有人还不知道剪枝,那我就弱弱地为大家补习一下吧qwq: .优化搜索顺序: 在一些搜索问 ...

  3. 洛谷P1731生日蛋糕&lpar;dfs&plus;剪枝&rpar;

    P1731 生日蛋糕 题目背景 7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层 生日蛋糕,每层都是一个圆柱体. 设从下往上数第i(1<=i<=M)层蛋糕是半径为R ...

  4. POJ - 1190 生日蛋糕 dfs&plus;剪枝

    思路:说一下最重要的剪枝,如果当前已经使用了v的体积,为了让剩下的表面积最小,最好的办法就是让R尽量大,因为V = πR 2H,A' = 2πRH,A' = V / R * 2 ,最大的R一定是取当前 ...

  5. &lbrack;POJ1190&rsqb;生日蛋糕&lt&semi;DFS&gt&semi;

    题目链接:http://poj.org/problem?id=1190 题看上去确实很复杂 涉及到半径面积这些,其实看着真的很头疼 但是除去这些就是剪枝优化的dfs算法 #include<cst ...

  6. 生日蛋糕 &lpar;poj1190&rpar; &lpar;dfs剪枝&rpar;

    [题目描述] 7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体. 设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为 ...

  7. poj1190 生日蛋糕(深搜&plus;剪枝)

    题目链接:poj1190 生日蛋糕 解题思路: 深搜,枚举:每一层可能的高度和半径 确定搜索范围:底层蛋糕的最大可能半径和最大可能高度 搜索顺序:从底层往上搭蛋糕,在同一层尝试时,半径和高度都是从大到 ...

  8. &ast;HDU1455 DFS剪枝

    Sticks Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

  9. POJ 3009 DFS&plus;剪枝

    POJ3009 DFS+剪枝 原题: Curling 2.0 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16280 Acce ...

随机推荐

  1. &lbrack;LeetCode&rsqb; Pow&lpar;x&comma; n&rpar; 求x的n次方

    Implement pow(x, n). 这道题让我们求x的n次方,如果我们只是简单的用个for循环让x乘以自己n次的话,未免也把LeetCode上的想的太简单了,一句话形容图样图森破啊.OJ因超时无 ...

  2. iterator and iterable

    前者是迭代器 后者是接口,List等继承这个接口

  3. dedecms模版制作活动的折叠菜单

    需要做成这种样式 url请求为这样: http://m03.com/plus/list.php?tid=19 这些菜单项都有对应的tid项,页面刷新后,应该将所有的菜单折叠起来,对于tid=19的菜单 ...

  4. c&plus;&plus;回调编程本质

    1. boost:bind获得一个函数对象,就像函数指针一样,这个行为可以作为回调 2. bosot:bind的函数对象可以保存别的对象的引用,回调对象的成员函数 3. boost:function是 ...

  5. UISlider小结

    滑块(UISlider)是常用的界面组件,能够让用户可以用可视化方式设置指定范围内的值,比如音量设置,比如灵敏度控制等诸如此类的用途. - (void)viewDidLoad { [super vie ...

  6. Cygwin-Cygwin ssh Connection closed by &colon;&colon;1 出错

    问题描写叙述: Cygwin好不easy安装好了ssh服务,第一连接没有问题,能够显示相关信息 $ ssh localhost Last login: Sat Jul 25 09:00:30 2015 ...

  7. 【算法导论】单源最短路径之Dijkstra算法

    Dijkstra算法解决了有向图上带正权值的单源最短路径问题,其运行时间要比Bellman-Ford算法低,但适用范围比Bellman-Ford算法窄. 迪杰斯特拉提出的按路径长度递增次序来产生源点到 ...

  8. 通过maven-assembly-plugin将Springboot项目打包成tar&period;gz压缩包,在Linux环境可执行脚本直接安装成系统服务

    1.在pom.xml中添加maven-assembly-plugin依赖,同时需将默认生成的spring-boot-maven-plugin依赖删除,否则最终打出的发行包启动会有问题 <plug ...

  9. &lpar;转)Spring Boot 2 &lpar;七&rpar;:Spring Boot 如何解决项目启动时初始化资源

    http://www.ityouknow.com/springboot/2018/05/03/spring-boot-commandLineRunner.html 在我们实际工作中,总会遇到这样需求, ...

  10. NSwag给api加上说明

    参考http://petstore.swagger.io 给controller加上description https://github.com/RSuter/NSwag/issues/1803 xm ...