poj1190生日蛋糕(dfs+剪枝)_c++体积npai,层数m固定,从底往上每层半径和高度逐层减少,现要求蛋糕外表面-程序员宅基地

技术标签: DFS  # 搜索  

->题目请戳这里<-

题目大意:一个m层的蛋糕,每层蛋糕均为圆柱体,总体积为n*PI,从下往上的层数满足每一层的半径和高度逐层严格递减。蛋糕最小表面积(不算底面)。(其中m、n以及每层的半径和高度均为整数,设最小表面积为s*PI,输出s)。如果不存在解,输出0。

题目分析:因为所有数据都是整数,层数不超过20层,每层的半径和高度有是单调递减的,因此可以用dfs遍历所有解,求最小的。用dfs逐层枚举该层的r,h。注意剪枝。

剪枝1:我们从m层往1层搜,即自下而上地搜,当搜到第i层的时候,考虑到最上一层最小的r和h均为1,因为都是整数,而每层半径和高度单调增加的,所以第i层的半径和高度的下界就是i,上界复杂些,对于半径而言,设搜到第I层的时候剩下体积为curv,用极限法,假设剩下的i层是一个圆柱,那么高度最小是1,那么最大半径就是sqrt(curv),而考虑到每层半径单调递减,所以第i层半径还应小于第i+1层半径减1,综上:第i层半径为第i+1层半径减1和sqrt(curv)之间的最小值,同理,第i层的高度上界也要考虑2个值,取第i+1层高度减1和curv之间的最小值。

剪枝2:搜到第i层的时候,剩下的i-1层每层的体积的最小值是一定的,我们从上往下数,最上面一层最小体积为1*1*1,第二层为2

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ophunter/article/details/8986869

智能推荐

BloomFilter应用与D-Lelft BloomFilter实现_dleft hash bloomfilter-程序员宅基地

文章浏览阅读812次。此篇文章是开发过程中对BloomFilter应用场景的一些介绍,另外项目中实现了D-Left BloomFilter,相关实现时一些注意的地方,简单介绍下!首先看一些应用场景:1.海量的黑白名单。2.爬虫抓取时重复的URL处理。3.数据key是否存在检测4.(一些面试题几十亿不重复整数中判断其中一个整数是否存在的问题,BitMap/BloomFilter能很好的解决)。。。_dleft hash bloomfilter

利用递归函数调用方式,将所输入的五个字符,以相反顺序打印出来-程序员宅基地

文章浏览阅读1k次。递归void palin(int n);int main(){ int i=5; printf("please input 5 numbers:"); palin(i); printf("\n"); } void palin(int n){ char next; if(n<=1) { next=getchar(); printf("\n"); putchar(nex..._要求利 递归函数调 的 式,将获取到所输 的5个字符,以相反顺序分别输

工作中常用的Git命令整理_工作中常用git命令-程序员宅基地

文章浏览阅读384次。背景码农10年,git命令还是经常使用的,这里整理下常用的git命令,用于新人上手。常用git命令一览:从远端拉一个分支:git checkout -b accuse origin/accusegit push origin HEAD -u 【将新建分支推送到远端服务器】从当前分支拉一个分支:git checkout -b accuse创建分支 git checkout -b new_branch 注意,new_branch的代码来自于当前分支切换分_工作中常用git命令

百兆以太网口通信速率_千兆以太网的传输速度-程序员宅基地

文章浏览阅读3.1k次。千兆以太网主流标准千兆以太网络技术早在上世纪90年代末就已成熟,其中,1995年国际标准化组织TIA/EIA颁布了1000Base-TX标准,该标准的目的是把双绞线用于千兆以太网中,其目的是在6类非屏蔽双绞线(UTP)上以1000Mbps速率传输100米。1000Base-TX基于4对双绞线,采用快速以太网中与100Base-TX标准类似的传输机制,是以两对线发送,两对线接收。由于每对线缆本身不进..._bi_da+

python图书管理系统基本增删改查函数实现_python实习报告图书-程序员宅基地

文章浏览阅读3.2k次,点赞3次,收藏55次。# 准备工作warning = ["傻", "蠢", "笨", "呆", "愚"] # 敏感词users = [{"user_name": "张三", "user_password": "18546732149"}, {"user_name": "manger", "user_password": "000000"}, {"user_name": "user1", "user_password": "123456"}]def menu(): while True: ._python实习报告图书

Python3.X 成功解决 module 'cv2' has no attribute 'xfeatures2d'_module 'cv2.cv2' has no attribute 'xfeatures2d-程序员宅基地

文章浏览阅读4.8k次。Python3.X 成功解决 module 'cv2' has no attribute 'xfeatures2d',建议安装3.3.0.10版本的contrib,更高版本的contrib里面专利保护了SIFT和SURF. 请执行 pip uninstall opencv-python 执行pip install opencv-contrib-python==3.3.0.10_module 'cv2.cv2' has no attribute 'xfeatures2d

随便推点

PAT 1151 LCA in a Binary Tree(30 分)- 甲级_lca in a binary tree 柳婼-程序员宅基地

文章浏览阅读8.3k次,点赞47次,收藏17次。The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.Given any two nodes in a binary tree, you are supposed to find their LCA.In..._lca in a binary tree 柳婼

HAL库教程10:定时器的PWM模式应用_mx_tim2_ini pwm-程序员宅基地

文章浏览阅读6.5k次,点赞13次,收藏41次。  本节通过定时器的PWM模式驱动无源蜂鸣器,来演奏一段音乐。本博客在掌机的系列教程中介绍过蜂鸣器的驱动原理,感兴趣的可以参考电子琴无源蜂鸣器驱动电路  蜂鸣器按照有无震荡源(不是电源),可以分为有源蜂鸣器和无源蜂鸣器。有源蜂鸣器上电就能工作,控制简单,但是只有一个音调。无源蜂鸣器需要单片机提供震荡源,虽然控制稍微复杂一点,但是可以发出不同频率的声音。PWM原理  根据我们的电路,引脚输..._mx_tim2_ini pwm

06第四章:Android生命周期_输出警告日志信息使用lo02类的( ) 方法-程序员宅基地

文章浏览阅读296次。Android程序的什么周期Android程序的什么周期是指在Android系统中,进程从启动到终止的所有阶段,即Android程序从启动到停止的全过程。Android程序的生命周期是由系统控制,而非程序自身直接控制。优先级从高到低:前台、可见、服务、后台、空进程前台进程:前台进程是Android系统中最重要的进程,它是与用户正在进行交互的进程。这样的进程重要性最高,一般情况下,系统中只有少数这样的进程。除非系统内存非常低,否则系统不会选择终止前台进程。满足前台进程的条件:进程正在最前段运行一个_输出警告日志信息使用lo02类的( ) 方法

Android Multimedia框架总结(二十六)利用FFmpeg进行解码直播流_multimedia android framework ffmpeg 系统图-程序员宅基地

文章浏览阅读8.4k次,点赞8次,收藏16次。转载请把头部出处链接和尾部二维码一起转载,本文出自逆流的鱼yuiop:http://blog.csdn.net/hejjunlin/article/details/59225373早在去年九月份时,写过一篇《手把手图文并茂教你用Android Studio编译FFmpeg库并移植》,今天用去年编译好的3.1.3的ffmpeg,进行在Android平台上解码直播流。看下Agenda:_multimedia android framework ffmpeg 系统图

UVA_156: Ananagrams_most crossword puzzle fans are used to anagrams — -程序员宅基地

文章浏览阅读683次。DescriptionMost crossword puzzle fans are used to anagrams--groupsof words with the same letters in different orders--for exampleOPTS, SPOT, STOP, POTS and POST. Some words however do not have thisa_most crossword puzzle fans are used to anagrams — groups of words with the

测试优惠券要怎么写测试用例?_设计一个购物优惠卷测试用例-程序员宅基地

文章浏览阅读1.4k次。使用会员抵扣券跳转到购买会员界面,支付时抵扣相应金额。使用方案抵扣券跳转到方案推荐的深度页面,选择方案支付时抵扣相应金额。查看可用的优惠券,可选择使用优惠券。我的优惠券页面点击某商品抵扣券后的“去使用”能否跳转到对应类型的商品页面。显示已失效的优惠券,显示优惠券类别,到期时间。失效优惠券按失效时间排序,显示前10的优惠券,剩下的优惠券不显示:优惠券选择页面:不可选择的优惠券置灰;支付页显示可用优惠券的数量,点击后跳转到选择优惠券页面,选择好优惠券后跳转到支付页。优惠券按照优惠额度排序。检测在我的页面优惠券点_设计一个购物优惠卷测试用例