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

题目链接

点此快速前往

题目总分析

就和我说的一样,这道题就是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;
}

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

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

相关文章

python5:基于多进程的并发编程、基于协程的并发编程的学习笔记

进程 为什么要使用多进程&#xff1f;——GIL的存在&#xff0c;多线程实际不是并发执行 将任务分为两类&#xff1a;IO密集型&#xff08;多线程&#xff09;CPU密集型&#xff08;多进程&#xff09; 多进程的基本用法 concurrent.futures.process.ProcessPoolExecutor#进…

李清照想老公了,人比黄花瘦

年轻时的风光无限&#xff0c;中年时的颠沛流离&#xff0c;晚年时的孤独寂寞&#xff0c;李清照的一生跌宕起伏&#xff0c;十分凄惨。 北宋的国破家亡&#xff0c;让李清照从活泼可爱的少女成为孤独的老妇人。 一、少女情思 少女时期&#xff0c;李清照有一次去游玩&#…

【Linux】误删除/home家目录怎么办? -- 此时ssh连接登录的就是此普通用户

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; &#x1f40b; 希望大家多多支…

Windows系统安装VNC客户端结合内网穿透实现公网远程连接Deepin桌面

文章目录 1. 安装x11vnc2. 本地远程连接测试3. Deepin安装Cpolar4. 配置公网远程地址5. 公网远程连接Deepin桌面6. 固定连接公网地址7. 固定公网地址连接测试 x11vnc是一种在Linux系统中实现远程桌面控制的工具&#xff0c;它的原理是通过X Window系统的协议来实现远程桌面的展…

AJAX-综合

文章目录 同步代码和异步代码回调函数地狱解决回调函数地狱Promise-链式调用async函数和awaitasync函数和await-捕获错误 事件循环宏任务与微任务Promise.all静态方法 同步代码和异步代码 同步代码&#xff1a;逐步执行&#xff0c;需原地等待结果后&#xff0c;才继续向下执行…

深入探索C语言动态内存分配:释放你的程序潜力

&#x1f308;大家好&#xff01;我是Kevin&#xff0c;蠢蠢大一幼崽&#xff0c;很高兴你们可以来阅读我的博客&#xff01; &#x1f31f;我热衷于分享&#x1f58a;学习经验&#xff0c;&#x1f3eb;多彩生活&#xff0c;精彩足球赛事⚽ &#x1f31f;感谢大家的支持&#…

【Java程序设计】【C00341】基于Springboot的药品管理系统(有论文)

基于Springboot的药品管理系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 项目获取 &#x1f345;文末点击卡片获取源码&#x1f345; 开发环境 运行环境&#xff1a;推荐jdk1.8&#xff1b; 开发工具&#xff1a;eclipse以及idea&…

力扣刷题31-33(力扣 0024/0070/0053)

今日题目&#xff1a; 24. 两两交换链表中的节点 题目&#xff1a;给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09; 思路&…

BOM 浏览器对象模型

文章目录 1. BOM 概述2.window 对象的常见事件窗口加载事件调整窗口大小事件 3.定时器setTimeout() 定时器案例&#xff1a;5秒后自动关闭的广告停止 setTimeout() 定时器setInterval() 定时器案例&#xff1a;倒计时停止 setInterval() 定时器案例&#xff1a;发送短信this 4.…

亚马逊云科技:企业如何开启生成式AI之旅?

如果要评选最近两年全球科技行业最热门的细分领域&#xff0c;那么生成式AI绝对会以遥遥领先的票数成为当仁不让的冠军。 然而眼见生成式AI发展得如火如荼&#xff0c;越来越多的企业却陷入了深深的焦虑&#xff1a;应该如何开启生成式AI之旅&#xff1f;又该怎样搭建大模型&am…

MySQL进阶-----Linux系统安装MySQL

目录 前言 一、准备工作 1. 准备一台Linux服务器 2. 下载Linux版MySQL安装包 3. 上传MySQL安装包 二、安装操作指令 1. 创建目录,并解压 2.安装mysql的安装包 三、开启mysql与密码修改 1.启动MySQL服务 2. 查询自动生成的root用户密码 3.修改root用户密码 四、创…

机器学习:智能时代的核心引擎

目录 一、什么是机器学习 二、监督学习 三、无监督学习 四、半监督学习 五、强化学习 一、什么是机器学习 机器学习是人工智能的一个分支&#xff0c;它主要基于计算机科学&#xff0c;旨在使计算机系统能够自动地从经验和数据中进行学习并改进&#xff0c;而无需进行明确…

MySQL下载及安装过程

MySQl 5.7 安装图解 目录 MySQl 5.7 安装图解 第一步 安装包 第二步 Mysql协议 第三步 安装前检查 第四步 安装 第五步 产品配置 第六步 安装完成 第一步 安装包 双击安装包文件 进行安装 第二步 Mysql协议 同意Mysql协议 , 选择 Server Only安装Mysql服务器即可 …

C语言 预处理器 注释 基本案例讲解

上文 程序设计语言与C语言发展 我们简述了 计算机语言的发展 以及编程语言与指令的概念 那么 今天 我们就来 初始C语言 并完成 第一个C语言案例 这里 我们需要完成 C语言 Hello World案例 以及 C语言程序举例 任何编程语言 开始的案例 都是 Hello World 所以说 Hello World 是…

Flutter 事件传递简单概述、事件冒泡、事件穿透

前言 当前案例 Flutter SDK版本&#xff1a;3.13.2 本文对 事件传递只做 简单概述&#xff0c;主要讲解&#xff0c;事件传递过程中可能遇到的问题解决&#xff0c;比如 事件冒泡、事件穿透&#xff1b; 不是我偷懒&#xff0c;是自认为没有这几位写的详细、仔细&#xff0c…

【Langchain-Chatchat】部署ChatGLM3-6B-32K教程

介绍 Langchain-Chatchat这个框架可以帮助我们更容易的部署大语言模型&#xff0c;之前也写过ChatGLM传统的部署教程&#xff0c;有兴趣的可以参考 【ChatGLM3】第三代大语言模型多GPU部署指南【ChatGLM2-6B】从0到1部署GPU版本 借助Langchain-Chatchat框架&#xff0c;可以…

入门linux之Ubuntu学习

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言1、介绍Ubuntu2、虚拟机目录解析3、常用指令ls&#xff1a;罗列当前目录文件信息对ls -l 的结果解析1.第一个字符2.每三个字符&#xff08;第一个字符后&#x…

新店开通后要做什么?一定要先做这几个设置,不然会影响店铺流量

大家好&#xff0c;我是电商花花。 新手做店如果没有一个完整的做店思路&#xff0c;很容易迷茫&#xff0c;没有方向&#xff0c;没有步骤&#xff0c;做完上一步不知道下一步该去干嘛。 今天给大家讲一下在开店后一定要做的几项基础搭建。 1、绑定官方账户 开店后在店铺后…

【ORB-SLAM3】在 Ubuntu20.04 上编译 ORM-SLAM3 并使用 D435i 运行测试

【ORB-SLAM3】在 Ubuntu20.04 上编译 ORM-SLAM3 并使用 D435i 运行测试 1 Prerequisites1.1 C11 or C0x Compiler1.2 Pangolin1.3 OpenCV1.4 Eigen3 2 安装 Intel RealSense™ SDK 2.02.1 测试设备2.2 编译源码安装 3 编译 ORB-SLAM34 使用 D435i 运行 ORB-SLAM34.1 运行4.2 运…