当前位置: 首页 > news >正文

洛谷 P1731 [NOI1999] 生日蛋糕

题目

题目链接

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

首先,输入输出都是正整数。先搞定输入,再判断条件,如果无解,输出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

【AC参考代码】

#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剪枝 生日蛋糕】

相关文章:

洛谷 P1731 [NOI1999] 生日蛋糕

题目 题目链接 自己没看题解写的&#xff0c;摸石头过河&#xff0c;解释一下 首先&#xff0c;输入输出都是正整数。先搞定输入&#xff0c;再判断条件&#xff0c;如果无解&#xff0c;输出0&#xff0c;否则输出蛋糕外表面面积Q&#xff08;这里用全局变量&#xff0c;开l…...

操作教程|使用MeterSphere对恒生UFX系统进行压力测试

恒生UFX&#xff08;United Finance Exchange&#xff0c;统一金融交换&#xff09;系统&#xff08;以下简称为“UFX系统”&#xff09;&#xff0c;是一款帮助证券公司统一管理外部接入客户的系统&#xff0c;该系统整体上覆盖了期货、证券、基金、银行、信托、海外业务等各类…...

算法中的数学知识

文章目录 算法中的数学知识约数约数个数约数之和 筛法求质数阶乘分解解法一解法二&#xff1a; 欧拉函数基本模板筛法求欧拉函数大数据幂的欧拉函数 快速幂费马小定理快速幂求逆元数论分块例题&#xff1a;[因数平方和](https://www.acwing.com/problem/content/4665/)分析:具体…...

2024高频前端面试题 Vue2 和 Vue3 篇

HTML和CSS篇&#xff1a;2024高频前端面试题 HTML 和 CSS 篇-CSDN博客 JavaScript 和 ES6 篇&#xff1a; 2024高频前端面试题 JavaScript 和 ES6 篇-CSDN博客 * Vue2 和 Vue3的区别&#xff1a; 1&#xff09;双向数据绑定原理的区别 2&#xff09;根节点的不同 Vue2只能一…...

vue,Promise备忘

网址 https://www.promisejs.org/ 记录 在Vue.js或者其他JavaScript项目中&#xff0c;Promise 是一种处理异步操作的标准机制&#xff0c;用于解决传统的回调地狱问题&#xff0c;提供了一种更优雅、链式调用的编程模型。Promise对象代表一个异步操作的结果&#xff0c;它可…...

软件测试工程师职位笔试知识点细节(2)

一、软件测试分为哪几个阶段&#xff0c;生命周期&#xff1f; 软件测试一般分为单元测试、集成测试和系统测试。 需求分析→测试计划→测试设计、软件开发→测试执行→测试评估 二、一条软件缺陷&#xff08;或者叫Bug&#xff09;记录都包含了哪些内容&#xff1f; 一条Bug…...

大数据冷热分离方案

数据冷热分离方案 1、背景 ​ 随着业务的发展&#xff0c;在线表中的数据会逐渐增加。常规业务都有冷热数据现象明显的特性&#xff08;需要访问的都是近期产生的热数据&#xff1b;时间久远的冷数据出于备份、备案溯源等诉求会进行在线保留&#xff09;。在业务表数据 量可控…...

Vue3中Vue Router的使用区别

在 Vue 3 中&#xff0c;useRouter 和 useRoute 是两个用于 Vue Router 的 Composition API 函数&#xff0c;它们的用途和返回的对象不同&#xff0c;接下来详细了解一下它们的区别以及如何正确使用它们。 useRouter useRouter 用于获取 router 实例&#xff0c;这个实例提供…...

Open CASCADE学习|读取STEP模型文件到XDE中

目录 1、XDE组件简介 2、读取STEP模型文件到XDE中的步骤 3、案例 1、XDE组件简介 Open CASCADE的XDE&#xff08;扩展数据交换&#xff09;组件是一个关键的工具&#xff0c;它允许用户通过转换附加到几何BREP&#xff08;边界表示&#xff09;数据的附加数据来扩展数据交换…...

flink:自定义数据分区

shuffle随机地将数据分配到下游的子任务。 rebalance用round robbin模式将数据分配到下游的子任务。 global把所有的数据都分配到一个分区。 partitionCustom: 自定义数据分区。 package cn.edu.tju.demo; import org.apache.flink.api.common.functions.; import org.apache…...

力扣图论篇

以下思路来自代码随想录以及官方题解。 文章目录 797.所有可能的路径200.岛屿数量130.被围绕的区域1020.飞地的数量 797.所有可能的路径 给你一个有 n 个节点的 有向无环图&#xff08;DAG&#xff09;&#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出&#xff08;不…...

图腾柱PFC工作原理:一张图

视屏链接&#xff1a; PFC工作原理...

MongoDB开启事务

MongoDB开启事务 配置单节点。到路径C:\Program Files\MongoDB\Server\4.0\bin 使用记事本以管理员权限打开文件mongod.cfg添加如下配置&#xff1a; replication:replSetName: rs02. 重启MongoDB服务 3. 重启后执行命令 rs.initiate()...

风车IM即时通讯系统APP源码DJ2403版完整苹果安卓教程

关于风车IM&#xff0c;你在互联网上能随便下载到了基本都是残缺品&#xff0c; 经过我们不懈努力最终提供性价比最高&#xff0c;最完美的版本&#xff0c; 懂货的朋友可以直接下载该版本使用&#xff0c;经过严格测试&#xff0c;该版本基本完美无缺。 1.宝塔环境如下: Ngin…...

新增流计算计数窗口,TDengine 3.2.3.0 八大板块功能更新

自发布以来&#xff0c;TDengine 3.0 版本在研发人员和社区用户的共同努力下不断优化&#xff0c;产品的稳定性和易用性获得了大幅提升&#xff0c;在知轮科技的智慧轮胎系统、黑格智能 3D 打印业务、韵达快递业务、中国地震台网中心、中移物联智慧出行场景等众多企业项目中获得…...

【架构笔记3】做“用心”之人

凡事就怕“用心”二字&#xff0c;但是用心做事&#xff0c;其实如果没有前提和详情&#xff0c;这本就是一句正确的废话&#xff0c;在一些项目开发和落地过程中&#xff0c;我也有了一些新的体会&#xff0c;自认为不是多余。 我觉得心这个词至少包含四个含义&#xff1a;“…...

前端加密面面观:常见场景与方法解析

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

突破编程_前端_JS编程实例(目录导航)

1 开发目标 目录导航组件旨在提供一个滚动目录导航功能&#xff0c;使得用户可以方便地通过点击目录条目快速定位到对应的内容标题位置&#xff0c;同时也能够随着滚动条的移动动态显示当前位置在目录中的位置&#xff1a; 2 详细需求 2.1 标题提取与目录生成 组件需要能够自…...

扩展学习|系统理解数字经济

文献来源&#xff1a;[1]肖静华,胡杨颂,吴瑶.成长品&#xff1a;数据驱动的企业与用户互动创新案例研究[J].管理世界,2020,36(03):183-205.DOI:10.19744/j.cnki.11-1235/f.2020.0041. [2]陈晓红,李杨扬,宋丽洁等.数字经济理论体系与研究展望[J].管理世界,2022,38(02):208-22413…...

前端学习之列表标签

目录 有序列表 结果 无序标签 结果 数据标签 结果 有序列表 &#xff08;注&#xff1a;注释是解释&#xff09; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Document</title> </…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...