洛谷 P1731 [NOI1999] 生日蛋糕

news/2024/4/13 11:16:53/文章来源:https://blog.csdn.net/CH3CH2CH4/article/details/136452973

题目

题目链接

自己没看题解写的,摸石头过河,解释一下

首先,输入输出都是正整数。先搞定输入,再判断条件,如果无解,输出0,否则输出蛋糕外表面面积Q(这里用全局变量,开long long)。

然后写dfs函数,函数形参先写了一个layer, r, h。这些数据是需要递归时传入的,在每一次的搜索中,r,h都会变。

先写结束条件,搜索层数layer与输入层数m相同时,return结束。后来写着写着又在形参加了两个变量,一个是奶油面积total_CreamArea(蛋糕外表面面积),一个是搜索中的总体积。结束条件中另外再加一个判断就是当总体积totalvolume = n时,取Q和奶油面积total_CreamArea的最小值来更新Q的值

写到这里就有问题了,遇到瓶颈。这个r,h的范围是多少呢?

#include <bits/stdc++.h>
using namespace std;int n, m; //蛋糕体积,层数
long long Q = 9e10;void dfs(int layer, int r, int h,int total_CreamArea, int totalvolume)
{if(layer == m) //层数 = 输入层数{if(totalvolume == n)Q = min(Q, total_CreamArea);return; //结束dfs}//for(int i = r; i>=0; i--)int newArea = total_CreamArea + 2*r*h; //加上侧面积,底面积就是第一层的大圆面积int newVolume = totalvolume + r*r*h; //加上新一层的体积dfs(layer+1, r, h, newArea, newVolume);
}int main()
{cin>>n>>m;dfs(1, )if(Q == 9e10)cout << 0 << endl;elsecout << minvolume << endl;
}

后来看了视频,还有罗老师的博客,才知道原来是这样确定r, h的范围的。当然剪枝也是不能少的,没有剪枝就会超时。

我是推不出来这个条件:2(n−v)/r+s≥ans,测试过没有这个条件也有70分!


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

【参考代码】

#include <bits/stdc++.h>
using namespace std;int n, m; //蛋糕体积,层数
int Q = 9e8;
int minVolume[16], minArea[16]; //用于剪枝void dfs(int layer, int r, int h,int total_CreamArea, int totalvolume)
{if(layer == 0) //层数 = 输入层数{if(totalvolume == n)Q = min(Q, total_CreamArea);return; //结束dfs}if(minVolume[layer] + totalvolume > n || totalvolume > n) //体积大于输入值return;if(total_CreamArea + minArea[layer] >= Q) //面积比最小面积还要大,舍去return;if(2*(n - totalvolume)/r + total_CreamArea >= Q) //2(n−v)/r+s≥ansreturn;for(int newR = min(r-1, (int)(sqrt(n-totalvolume)) ); newR >= layer; newR--){if(layer == m) //上表面积,从上往下看就是一个圆total_CreamArea = newR * newR;//体积公式求hfor(int newH = min(h-1, (n-totalvolume)/(newR * newR) ); newH >= layer; newH--){int newArea = total_CreamArea + 2*newR*newH; //加上侧面积,底面积就是第一层的大圆面积int newVolume = totalvolume + newR*newR*newH; //加上新一层的体积dfs(layer-1, newR, newH, newArea, newVolume);}}}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){minVolume[i] = minVolume[i-1] + i*i*i; //R^3minArea[i] = minArea[i-1] + 2*i*i; //2*R^2}dfs(m, 9e8, 9e8, 0, 0);if(Q == 9e8)cout << 0 << endl;elsecout << Q << endl;
}

看视频吧,视频肯定比我讲得清楚。视频链接:【B24 DFS剪枝 生日蛋糕】

【B24 DFS剪枝 生日蛋糕】

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997934.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【愚公系列】2024年02月 《网络安全应急管理与技术实践》 013-网络安全应急技术与实践(Web层-XSS钓鱼攻击)

🏆 作者简介,愚公搬代码 🏆《头衔》:华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主,腾讯云内容共创官,掘金优秀博主,51CTO博客专家等。 🏆《近期荣誉》:2022…

全志D1s裸机开发之体验第一个程序

体验第一个程序 2.1 编译烧录运行 2.1.1 编译 先进入源码目录&#xff0c;打开 Git Bash&#xff0c;如下图操作&#xff1a; 然后在 Git Bash 中执行 make 命令&#xff0c;可以生成 benos_payload.bin 文件&#xff0c;如下图所示&#xff1a; 2.1.2 烧录运行 使用 2 条 …

Leetcode HOT150

55. 跳跃游戏 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1 …

用云手机进行舆情监测有什么作用?

在信息爆炸的时代&#xff0c;舆情监测成为企业和政府决策的重要工具。通过结合云手机技术&#xff0c;舆情监测系统在品牌形象维护、市场竞争、产品研发、政府管理以及市场营销等方面发挥着关键作用&#xff0c;为用户提供更智能、高效的舆情解决方案。 1. 品牌形象维护与危机…

基于java ssm springboot女士电商平台系统

基于java ssm springboot女士电商平台系统源码文档设计 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末…

第107讲:Mycat实践指南:取模分片下的水平分表详解

文章目录 1.使用取模分片水平分表2.水平分表取模分片案例2.1.准备测试的表结构2.2.配置Mycat实现范围分片的水平分表2.2.1.配置Schema配置文件2.2.2.配置Rule分片规则配置文件2.2.3.配置Server配置文件2.2.4.重启Mycat 2.3.写入数据观察水平分表效果 1.使用取模分片水平分表 平…

2024新疆专升本考试报名教程详解

2024新疆专升本报名时间已经开始了&#xff0c;想要参加考试报名的同学可以提前准备好报名照

产品推荐 - GX-SOPC-5CEFA5-M484 FPGA核心开发板

● 核心板采用8层板精心设计 ● FPGA&#xff1a;采用Intel&#xff08;ALTERA&#xff09; Cyclone V 5CEFA5&#xff0c;Les为77K&#xff0c;内嵌存储器为4460Kb&#xff0c;硬件乘法器为300个&#xff0c;最大等效门数约2300万门&#xff1b;新增DSP Block&#xff08;150…

新版AndroidStudio的Gradle窗口显示task list not built 问题解决

在使用新版AndroidStudio时&#xff0c;会出现&#xff0c;Task List not built 的问题。如果你记得task的名字&#xff0c;当然可以 直接通过命令 gradle taskname 或者 ./gradlew taskName直接执行即可&#xff0c;但是若是记不住&#xff0c;还是把这个任务构建处理比较好用…

鸿蒙Harmony 时代的跨端方案

终端系统的数量和种类不断增长&#xff0c;开发者面临着多平台开发的挑战。以往开发者一般只需要维护iOS、android、MacOS、windows几个主流核心终端操作系统即可&#xff0c;但是随着信创化的趋势&#xff0c;统信、麒麟、鸿蒙等操作系统也开始崛起&#xff0c;后续可能还会涌…

智慧城市的新引擎:物联网技术引领城市创新与发展

目录 一、引言 二、物联网技术与智慧城市的融合 三、物联网技术在智慧城市中的应用 1、智慧交通管理 2、智慧能源管理 3、智慧环保管理 4、智慧公共服务 四、物联网技术引领城市创新与发展的价值 五、挑战与前景 六、结论 一、引言 随着科技的日新月异&#xff0c;物…

FPGA时序约束与分析--数据到达路径和数据需求路径

文章目录 前言一、定义二、时序模型三、公式推导 前言 时序约束的定义–设计者根据实际的系统功能&#xff0c;通过时序约束的方式提出时序要求&#xff1b; FPGA 编译工具根据设计者的时序要求&#xff0c;进行布局布线&#xff1b;编译完成后&#xff0c; FPGA 编译工具还需…

Java网络通信TCP

目录 TCP两个核心类 服务端 1.用ServerSocker类创建对象并且手动指定端口号 2.accept阻塞连接服务端与客户端 3.给客户端提供处理业务方法 4.处理业务 整体代码 客户端 1.创建Socket对象&#xff0c;并连接服务端的ip与端口号 2.获取Socket流对象&#xff0c;写入数据…

HAproxy

四层&#xff1a; - LVS&#xff1a;Linux Virtual Server - Nginx&#xff1a; - HAProxy&#xff1a;High Availability Proxy 七层: - HAProxy - Nginx 硬件&#xff1a; - F5 https://f5.com/zh- Netscaler https://www.citrix.com.cn/product…

能量不等式证明

波动方程初值问题能量不等式的证明 Gronwall 不等式 若非负函数 G ( τ ) G(\tau) G(τ) 在 [ 0 , T ] [0,T] [0,T] 上连续可微&#xff0c; G ( 0 ) 0 G(0)0 G(0)0&#xff0c;且对 τ ∈ [ 0 , T ] \tau\in[0,T] τ∈[0,T]满足 d G ( τ ) d τ ≤ C G ( τ ) F ( τ …

【PyQt】16-剪切板的使用

文章目录 前言一、代码疑惑快捷键 二、现象2.1 复制粘贴文本复制粘贴 2.2 复制粘贴图片复制粘贴 2.3 复制粘贴网页 总结 前言 1、剪切板的使用 2、pycharm的编译快捷键 3、类的属性和普通变量的关系 4、pyqt应该养成的编程习惯-体现在代码里了&#xff0c;自己看看。 一、代码…

Bert Encoder和Transformer Encoder有什么不同

前言&#xff1a;本篇文章主要从代码实现角度研究 Bert Encoder和Transformer Encoder 有什么不同&#xff1f;应该可以帮助你&#xff1a; 深入了解Bert Encoder 的结构实现深入了解Transformer Encoder的结构实现 本篇文章不涉及对注意力机制实现的代码研究。 注&#xff1a;…

CentOS7 利用remi yum源安装php8.1

目录 前言remi yum源remi yum源 支持的操作系统remi yum源 支持的php版本 安装epel源安装remi源安装 php8.1查看php版本查看php-fpm服务启动php-fpm服务查看php-fpm服务运行状态查看php-fpm服务占用的端口查看 php8.1 相关的应用 前言 CentOS Linux release 7.9.2009 (Core) …

maven项目引入私有jar,并打包到java.jar中

私有jar存放位置 maven依赖 <dependency><groupId>com.hikvision.ga</groupId><artifactId>artemis-http-client</artifactId><version>1.1.10</version><scope>system</scope><systemPath>${project.basedir}/s…

【ETCD】简介安装常用操作---图文并茂详细讲解

目录 一 简介 1.1 etcd是什么 1.2. 特点 1.3. 使用场景 1.4 关键字 1.5 工作原理 二 安装 2.1 etcd安装前介绍 2.2 安装 2.3 启动 2.4 创建一个etcd服务 三 常用操作 一 简介 1.1 etcd是什么 etcd是CoreOS团队于2013年6月发起的开源项目&#xff0c;它的目标是构建…