(DFS + 剪枝)【洛谷P1731】 [NOI1999] 生日蛋糕

news/2024/4/15 7:16:13

题目链接

点此快速前往

题目总分析

就和我说的一样,这道题就是DFS加剪枝,非常好的一道题

我起初看到这个题我根本不知道怎么dfs才是正确的, 感觉变量有这么多不确定的,每一层的半径,每一层的高度,而且这之间的联系在刚看到这个题的我看来十分的小,应该是我太菜了导致的

深入往下看,你就发现实际上这道题已经告诉了你每一层的限制了,并不是完全无从下手,至少你知道这一层的半径和高度一定小于等于它底下那一层的半径和高度-1,所以我们不难想象出dfs的做法:最下面那一层的半径最大值是假设只有一层,n-1就是它起初的最大值,那么最小值就是总共的层数,,因为每一层都要至少要少1,所以最大的那一层半径和高度肯定就最小值就是层数

为什么不遍历高度而是半径呢?

你稍微列一下式子你就会发现,实际上半径对总面积的影响程度要高于高度的,所以想要最小,一定是从半径入手。

总体积 n = ∑ i = 1 m R i ∗ H i 总体积 n = \sum_{i = 1}^{m} R_i * H_i 总体积n=i=1mRiHi

总面积 m = R 0 2 + ∑ i = 1 m R i 2 ∗ H i 总面积 m = R_0^2 + \sum_{i=1}^{m} R_i^2 * H_i 总面积m=R02+i=1mRi2Hi

为什么总面积前面有个 R 0 2 R_0^2 R02

简单想想,虽然是每个圆柱都被另一个比它小的圆柱盖住了一个圆的面积,但是你从这个蛋糕的最上面去看,就不难发现,最上面的面积和其实就是最底层圆柱的顶面面积。

看到这可能已经想要去写了,不过先停一下
这道题dfs搜索只是第一步,而更重要的是剪枝,由于处理数据的量也是非常大的,如果不进行一些优化就没办法顺利进行

首先既然我们知道每一层最小的半径和高,那么我们就不难算出来到每一层为止,最小的体积和最小的面积分别是多少

有了上述的信息之后,我们在准备遍历之前可以先判断一下

  1. 如果此时此刻接下来几层的最小面积加上此时的面积已经大于等于当前的最优解你,那就没有必要去遍历了。
  2. 同样,接下里几层的最小体积加上此时的体积已经大于要求的总体积n,那么也没必要去遍历了
  3. 这个是比较难想的,我们是从最下层遍历到最上层的,也就是说假设此时此刻遍历的层数半径为r,包括这一层之前的总体积为v以及总面积是s , 总共的蛋糕体积是n,那么如果 2 ∗ ( n − v ) / r > 此时的最优解 2 * (n - v) / r > 此时的最优解 2(nv)/r>此时的最优解,同样也没有遍历下去的必要了

前两个好理解,第三个是什么东西啊?
很好我开始看到的时候也非常困惑,接下来推导一下你就懂了

从m开始now是已经搭建好的层数了,now-1就是接下来之后的层

接下里的面积应该是 ∑ i = 1 n o w − 1 R i 2 ∗ H i 接下里的面积应该是\sum_{i = 1}^{now - 1} R_i^2 * H_i 接下里的面积应该是i=1now1Ri2Hi
看一下我第三条公式,你可以清楚的发现, R i R_i Ri全部都小于当前这一层的 r 所以,接下里的面积必然比 2 ∗ ( n − v ) / r 2 * (n - v) / r 2(nv)/r大,如果这个面积都大于等于最优解了,那么就不需要遍历了

接下来就是代码实现了,基本思路已经写完,代码中有不理解的部分可以评论区提问一下或者私信。

总代码

#include<bits/stdc++.h>
using namespace std;
const int N = 25 , INF = 0x3f3f3f3f;
int n,m;
int ans = INF;
int Mins[N] , Minv[N];
void dfs(int now,int r,int h,int s,int v)
{int MH = h;if(now == 0){if(v == n){ans = min(ans, s);}return ;}if(Mins[now-1] + s >= ans) return;if(Minv[now-1] + v > n) return;if(2 * (n - v) / r + s >= ans) return;for(int i=r-1;i>=now;i--){if(now == m) s = i * i;MH = min(h-1 , (n - Minv[now-1] - v) / i / i);for(int j = MH ; j >= now ; j--){dfs(now-1 , i , j , s + 2 * i * j , v + i * i * j);}}
}int main()
{cin >> n >> m;for(int i=1;i<=m;i++){Mins[i] = Mins[i-1] + i * i * 2;Minv[i] = Minv[i-1] + i * i * i;}dfs(m,n,n,0,0);if(ans == INF) cout << 0 << '\n';else cout << ans << '\n';return 0;
}

http://www.ppmy.cn/news/1394239.html

相关文章

密码学之哈希碰撞和生日悖论

哈希碰撞 哈希碰撞是指找到两个不一样的值&#xff0c;它们的哈希值却相同 假设哈希函数的取值空间大小为k &#xff0c;计算次数为n 先算每个值不一样的概率P’ 所以至少两个值相同(即存在哈希碰撞)的概率P为 生日悖论 假设班里有50个人&#xff0c;求班里至少两个人相同…

2024网络安全数据安全加固类资料合集

精品推荐-2024网络安全&数据安全加固类资料合集&#xff08;36份&#xff09;.zip 一、基线检查脚本 Linux基线检查.zip Windows基线检查V1.4.zip Windows安全基线核查加固助手.zip 基线核查脚本.zip 二、安全加固规范 AIX主机操作系统安全加固规范.doc Apache系统安全加…

js 获取对象的属性名(key)列表

js 获取对象的属性名(key)列表 keys() 方法获取 values()可以获取键值列表 const person {name: "Bill",age: 19,eyeColor: "blue" }; const keys Object.keys(person); console.log(keys)// [name, age, eyeColor]for in 语句获取 const person {na…

基于springboot+vue的宠物商城网站

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

MySQL数据库——单表查询、连接查询、子查询

头歌MySQL数据库代码、答案&#xff0c;单表查询、连接查询、子查询 目录 MySQL数据库 — 单表查询&#xff08;一&#xff09; 第一关&#xff1a;基本查询语句 第二关&#xff1a;带 IN 关键字的查询 第三关&#xff1a;带 BETWEEN AND 的范围查询 MySQL数据库 — 单表…

解决前端跨域问题

前端跨域问题 该问题是由于前端的服务路径或端口和后台的不一致所导致的 Springboot跨域设置 import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.web.cors.CorsConfiguration; …

sqlalchemy和moke生成实体类(一)

前言 如果通过java生成实体类&#xff0c;可以通过mybatis或者mybatis-plus的generator。 而sqlalchemy也可以生成实体类&#xff0c;通过sqlalcodegen或者flask-sqlalcodegen。 使用flask-sqlalcodegen生成实体类 建表 建立学生表&#xff0c;如下。 create table stude…

Cache缓存:HTTP缓存策略解析

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【GitHub】2FA(双重身份验证)

无需额外设备完美插件处理&#xff1a;Authenticator Crx搜搜&#xff1a;https://www.crxsoso.com/ 或者google查询&#xff1a;Authenticator

AcWing 796. 子矩阵的和

这个题的重点是仿照一维的数组&#xff0c;所以a[N][N]也是从1索引开始的。画个图举个例子就非常清晰了 之所以不好理解是因为没画格子&#xff0c;一个格子代表一个点&#xff0c;就很好理解了。 java代码&#xff1a; import java.io.*; public class Main{static int N 1…

C语言经典算法-9

文章目录 其他经典例题跳转链接46.稀疏矩阵47.多维矩阵转一维矩阵48.上三角、下三角、对称矩阵49.奇数魔方阵50.4N 魔方阵51.2(2N1) 魔方阵 其他经典例题跳转链接 C语言经典算法-1 1.汉若塔 2. 费式数列 3. 巴斯卡三角形 4. 三色棋 5. 老鼠走迷官&#xff08;一&#xff09;6.…

浏览器强缓存和弱缓存的主要区别

浏览器强缓存与弱缓存 浏览器的缓存机制主要分为两种&#xff1a;强缓存与协商缓存&#xff08;也称弱缓存&#xff09;。 强缓存 强缓存是指浏览器在请求一个资源时&#xff0c;不与服务器发生通信&#xff0c;直接从本地缓存中获取资源。如果存在有效的强缓存&#xff0c;…

Java面试题:设计一个线程安全的单例模式,并解释其内存占用和垃圾回收机制;使用生产者消费者模式实现一个并发安全的队列;设计一个支持高并发的分布式锁

Java深度面试题&#xff1a;设计模式、内存管理与并发编程的综合考察 随着Java技术的不断发展&#xff0c;对Java开发者的技术要求也在不断提高。设计模式、内存管理、多线程工具类以及并发工具包和框架等都是Java开发者必须掌握的核心知识点。本文将通过三道综合性的面试题&a…

linux下实现两台服务器下文件夹文件实时同步

背景&#xff1a; 现在有服务器A&#xff0c;和服务器B&#xff0c;现在需要把服务器A的 /usr/tmp目录下的内容时刻和服务器B的内容进行时刻同步&#xff0c;当A服务器的该目录出现增删改时&#xff0c;保障B的该目录下的内容和A时刻一样&#xff0c;其中B的IP为&#xff1a;1…

抖音视频关键词批量采集工具|视频无水印爬虫下载软件

抖音视频关键词批量采集工具&#xff1a; 最新推出的抖音视频关键词批量采集工具&#xff0c;为您提供一种便捷的方式通过关键词搜索和提取符合条件的视频内容。以下是详细的操作说明和功能解析&#xff1a; 操作说明&#xff1a; 进入软件后&#xff0c;在第一个选项卡页面…

用Compute Shader处理图像数据后在安卓机上不能正常显示渲染纹理

1&#xff09;用Compute Shader处理图像数据后在安卓机上不能正常显示渲染纹理 2&#xff09;折叠屏适配问题 3&#xff09;Prefab对DLL中脚本的引用丢失 4&#xff09;如何优化Unity VolumeManager中的ReplaceData 这是第378篇UWA技术知识分享的推送&#xff0c;精选了UWA社区…

计算机视觉研究方向

计算机视觉是一个广泛且快速发展的领域&#xff0c;涵盖了多种研究方向和技术。主要的研究方向包括图像处理、目标检测与识别、图像生成、三维视觉、行为识别、深度学习与计算机视觉、多媒体分析、视频理解、风格化、全向视觉传感器等。这些研究方向和技术不断进步&#xff0c;…

第四章:java的常用类

系列文章目录 文章目录 系列文章目录前言一、包装类1.1 包装类和基本数据的转换1.2 包装类型和 String 类型的相互转换1.3 Integer 类和 Character 类的常用方法1.4 Integer 类和 的用法 二、String类2.1 String 类的理解和创建对象2.2 创建 String 对象的两种方式2.3 两种创建…

用C++做一个植物大战僵尸

制作一个完整的“植物大战僵尸”游戏是一个非常大的项目&#xff0c;涉及图形渲染、碰撞检测、用户输入处理、音效、动画、游戏逻辑等多个方面。由于这个话题非常广泛&#xff0c;我可以提供一个简化的版本或者一个框架来启动你的项目。 以下是一个简化的框架&#xff0c;帮助…

Python实战:信号处理:signal模块

1. 引言 在Unix-like操作系统中&#xff0c;信号是一种异步通知机制&#xff0c;用于在特定事件发生时通知进程。信号可以由内核、其他进程或进程自身发送。Python的signal模块提供了对Unix信号处理的接口&#xff0c;允许Python程序捕获和处理信号。掌握信号处理对于编写健壮…
最新文章