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

P1731 生日蛋糕 做题记录

洛谷P1731 生日蛋糕 做题记录

题意简述

一个生日蛋糕由几个圆柱体组成,每个圆柱体的底面半径和高从下到上严格递减,现给出蛋糕的体积 N pi 以及层数 M,试求蛋糕的最小表面积。

思路速通

基本为 DFS ,对于每层的半径以及高度进行枚举,然后增加一些剪枝。
以下为较为重要的剪枝:

  1. 体积明显不够剩下的层数进行分配时 return;
  2. 当前体积已经>n时return;
  3. 当前已经累加出的表面积明显大于当前已经算出的最小总表面积时 return;
  4. 当前已经累加出的表面积与剩下部分最小的表面积之和明显打与当前已经算出的最小总表面积时 return ;

代码实现

#include<bits/stdc++.h>
#define bot r[1]*r[1]
using namespace std;
const int inf=2147483647;
int n,m;
int r[25],h[25];
int minn=inf;void dfs(int now,int v_last,int s,int last_m){if(last_m<0){return ;}if(v_last<0){return ;}//体积>n时剪枝if(s>=minn){return ;}if(v_last==0&&!last_m){s+=bot;minn=min(minn,s);return ;}if(s+last_m*2+bot>minn){return ;}//当前表面积与剩余最小表面积相加之和大于当前已经算出的最小总表面积时剪枝if(v_last>r[now-1]*r[now-1]*h[now-1]*last_m){return ;}//当前剩余体积不够剩余的最大体积分配时剪枝for(int i=r[now-1]-1;i>=last_m;i--){//枚举半径for(int j=h[now-1]-1;j>=last_m;j--){//枚举高度if(v_last>=i*i*j&&now+1<=m+1){r[now]=i;h[now]=j;dfs(now+1,v_last-i*i*j,s+2*i*j,last_m-1);r[now]=0;h[now]=0;}}}return ;
}int main() {scanf("%d %d",&n,&m);if(m==1){//只有一层时特判//朴素暴力for(int i=n;i>=1;i--){for(int j=n;j>=1;j--){if(i*i*j==n){minn=min(minn,2*i*j+i*i);}}}printf("%d",(minn==inf?0:minn));return 0;}r[0]=(int)sqrt(n);h[0]=(int)sqrt(n);dfs(1,n,0,m);printf("%d",(minn==inf?0:minn));//最终还要判断是否有方案return 0;
}
http://www.hskmm.com/?act=detail&tid=18863

相关文章:

  • 如何有效提升代码覆盖率:从单元测试到集成测试的实践指南
  • Spring知识点(2)
  • 超越实习期的AI自动化工具:播客工作流与Slack导出器实战
  • 调度器的各项指标以及计算方式
  • 浅谈dsu on tree
  • JavaDay10
  • 昇腾多机推理极速上手:10倍简化的 DeepSeek R1 超大规模模型部署
  • python开始exe应用程序初级教程
  • B站油管抖音一键笔记
  • 介绍自己
  • pycharm更换国内源
  • 基于Python+Vue开发的反诈视频宣传管理系统源码+运行步骤
  • 0voice-2.2.1-服务器百万并发实现
  • 微服务去掉认证的功能
  • INNER JOIN LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN
  • 进程调度的时机,切换与过程
  • 深入解析:六维力传感器材质选择:影响性能与精度的关键因素
  • 按键精灵安卓/ios辅助工具,脚本开发新手教程ui界面介绍 - 教程
  • P3197fwx - FanWenxuan
  • 2025年AI大模型赋能智能座舱研究报告:技术、资本与市场|附20+份报告PDF、数据仪表盘汇总下载
  • 专题:2025年AI Agent智能体行业洞察报告|附110+份报告PDF、数据仪表盘汇总下载
  • 开启我的Java旅程
  • MYSQL: 时间戳演示
  • 自动化测试用例结构分析
  • 谷歌新款具身智能模型 Gemini Robotics 1.5 和 Gemini Robotics-ER 1.5
  • 完整教程:测试自动化教程:Parasoft如何流重定向与单元测试自动化
  • 用 Zig 实现英文数字验证码识别
  • 用 Crystal 实现英文数字验证码识别工具
  • 基于 Nim 的英文数字验证码识别工具实现
  • 完整教程:数组(Java基础语法)