首页 > 其他分享 >英杰们的蛋糕塔(dfs)(难)

英杰们的蛋糕塔(dfs)(难)

时间:2023-07-24 23:55:49浏览次数:32  
标签:英杰 表面积 int minsur leftV dfs 体积 蛋糕 surArea

 

题解:

  这道题的关键是找到状态转移方程,从最底层(n)开始,计算上面全部(n, n - 1, n - 2 …… 1)层的总表面积和总体积,从而来确定使表面积最小的S

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define S(r) ((r) * (r))          // 底面积
 4 #define C(r, h) (2 * (r) * (h))   // 侧面积
 5 #define V(r, h) ((r) * (r) * (h)) // 体积
 6 #define VRC(r, v) (2 * v / (r))   // 根据体积和半径计算侧面积
 7 
 8 // 查表法计算各层的体积与侧面积区间下界
 9 int sumMinV[27], sumMinC[27];
10 
11 const int INF = 0x7ffffff;
12 int v, n, minsur = INF; // 最小表面积
13 
14 //  从最底层到最高层搜索
15 //  从第i层开始搭建表面积最小的蛋糕塔
16 //  其底半径和高的最大值为搜索前一层的半径preR和高preH
17 //! leftV为剩余的总体积,surArea为该塔施工过程中累计的表面积
18 void dfs(int i, int preR, int preH, int leftV, int surArea)
19 {
20     if (i == 0) // 抵达最高层
21     {
22         if (leftV == 0 && surArea < minsur)
23             minsur = surArea;
24         return;
25     }
26     //*********************
27     // 预估此路径剩余体积的最小表面积值,若超过全局变量的最小值,则无需继续搜索
28     if (preR > 1 && VRC(preR - 1, leftV) + surArea >= minsur)
29         return;
30 
31     // 剩余体积小于i层的最小体积,体积余量不足
32     if (leftV < sumMinV[i])
33         return;
34 
35     // 累计表面积 + 最小表面积 > 全局最小表面积
36     if (surArea + sumMinC[i] >= minsur)
37         return;
38     //*********************
39     // 以上3步为剪枝操作
40 
41     // 枚举所有的R和H,深搜
42     for (int r = preR - 1; r >= i; --r)
43     {
44         if (i == n)
45             surArea = S(r); // 最底层的底面积
46 
47         // 确定高度枚举范围的上界
48         int H_max = (1.0 * leftV / S(r)) ; // 剩余体积除以底面积为高
49         if (H_max > preH - 1)
50             H_max = preH - 1; // 高的最大值
51 
52         for (int h = H_max; h >= i; --h)                          // 枚举所有的高,因为至少有i层,所以高的下界是i
53             dfs(i - 1, r, h, leftV - V(r, h), surArea + C(r, h)); // 根据接口传递参数
54     }
55 }
56 
57 int main()
58 {
59     cin >> v >> n;
60     // 从顶层往下层递推计算,最高层为0
61     sumMinV[0] = sumMinC[0] = 0;
62 
63     for (int i = 1; i <= n; ++i)
64     {
65         // 所有半径和高度都是正整数,所以可得下面的递推式
66         sumMinC[i] = sumMinC[i - 1] + C(i, i); // 第i层之上的最小侧面积之和
67         sumMinV[i] = sumMinV[i - 1] + V(i, i); // 第i层之上的最小体积之和
68     }
69 
70     // 最底层最大的H和R
71     // 底半径为n(最小值)的时候h(高度)最大
72     int maxH = (v - sumMinV[n - 1]) / S(n) + 1; // 不加1也能过,为什么?
73     // 高度为1的时候圆柱的半径最大
74     int maxR = sqrt(double((v - sumMinV[n - 1]) + 1)); // 这里也是不加1也能过
75     /*
76     这里加1是为了避免在计算最大底半径时出现精度误差。具体来说,假设最大底半径为maxR,最底层的底面积为S(n),当前已经搭建的层数为k,累计体积为sumV,那么最大底半径至少需要满足以下条件:
77         S(n) * maxR * maxR <= v - sumV
78 
79     其中,v是总体积,sumV是当前已经搭建的蛋糕塔的总体积。
80     由于计算机在处理浮点数时存在精度误差,因此在计算S(n) * maxR * maxR时可能会出现略微小于v - sumV的情况,导致计算出的maxR比实际值小一些。为了避免这种情况,可以在计算S(n) * maxR * maxR时加上1,使得计算出的maxR略微大于实际值,从而避免精度误差。
81 
82     需要注意的是,这种精度误差通常只会在极端情况下出现,对于大多数情况来说,不加1也不会导致结果错误。因此,这里加1只是为了提高程序的健壮性和鲁棒性。
83     */
84 
85     minsur = INF; // 初始化
86     dfs(n, maxR, maxH, v, 0);
87 
88     if (minsur == INF)
89         cout << 0 << endl;
90     else
91         cout << minsur << endl;
92     return 0;
93 }

 

标签:英杰,表面积,int,minsur,leftV,dfs,体积,蛋糕,surArea
From: https://www.cnblogs.com/nijigasaki14/p/17578663.html

相关文章

  • linux下载安装fastdfs和fastdfs与nginx整合、springboot访问fastdfs
    文章目录需求分析分布式文件系统1FastDFS安装FastDFS和nginx整合2.整合java访问fastdfs服务文件上传查询下载测试整合springboot需求分析搭建fastDFS文件服务器1)安装fastDFStracker和storage2)在storageserver上安装nginx在storageserver上安装nginx的目的是对外通过http访问......
  • HDFS High Availability
    HDFSHighAvailabilityHDFSHighAvailabilityPurposeNote:UsingtheQuorumJournalManagerorConventionalSharedStorageBackgroundArchitectureHardwareresourcesDeploymentConfigurationoverviewConfigurationdetailsDeploymentdetailsAdministrativecommandsA......
  • HDFS High Availability Using the Quorum Journal Manager
    HDFSHighAvailabilityUsingtheQuorumJournalManagerHDFSHighAvailabilityUsingtheQuorumJournalManagerPurposeNote:UsingtheQuorumJournalManagerorConventionalSharedStorageBackgroundArchitectureHardwareresourcesDeploymentConfigurationoverv......
  • 组合的输出 dfs
    #include<bits/stdc++.h>usingnamespacestd;inta[101];intm,n;voids(intk){inti;if(k>m){for(i=1;i<=m;i++){cout<<setw(3)<<a[i];}cout<<endl;return;}for......
  • 搜索(DFS/BFS)
    广度优先搜索(BFS)基本要点: -利用队列(先进先出) -一层一层搜索 -适合于连通块的搜索 -任何的BFS都可以转化为对树的广搜基本流程: -选择搜索的起点,起点入队,起点标记为已访问 -队列非空时,循环出队,每次出队将与出队元素连通的且未访问过的元素依次入队,并......
  • 冷门科技 —— DFS 序求 LCA
    Updateon2023.7.17:该技巧目前已知的最早来源:skip2004。Updateon2023.7.17:比较时,取时间戳较小的结点也是正确的,不用记录深度。DFS序求LCA无论是从时间常数,空间常数还是好写程度方面均吊打欧拉序。定义DFS序表示对一棵树进行深度优先搜索得到的结点序列,而时间戳DFN......
  • 小明以 hadoop 用户身份在 HDFS 上 hadoop 目录下创建 expl 目录时,发现该目
    使用Hadoop创建目录引言Hadoop是一个开源的分布式计算框架,提供了可靠性和高可扩展性的存储和处理大数据的能力。其中的分布式文件系统HDFS(HadoopDistributedFileSystem)是Hadoop的核心组件之一,用于存储和管理海量数据。在HDFS上进行目录和文件的操作是使用Hadoop命令行工具或者......
  • SaeweedFS操作
    #mdir存储元数据的数据目录#port监听端口#peers主节点ip:端口#defaultReplication备份策略#ip服务器ip#garbageThreshold清空和回收空间的阈值#maxCpu最大cpu数量,0是所有#pulseSeconds心跳检测的时间间隔单位为秒#ip.bind绑......
  • Docker安装的fastdfs基于不同服务器的数据迁移
    首先,基于docker搭建新的fastdfs中间件,参考地址为:https://blog.csdn.net/ming19951224/article/details/126933299然后将原服务器的storage文件夹下的data文件夹进行备份,打包成bak.zip 将bak.zip下载后上传到新服务器的storage文件夹下 使用unzip解压缩bak.zip,然后进入data.......
  • 创新 = 颠覆?AI创新如何做大蛋糕
    本文分享自华为云社区《创新=颠覆?AI创新如何做大蛋糕》,作者:华为云PaaS服务小智。最近随着AI的风靡,各行各业都充斥着近乎疯狂的言论,“AI必将替代一切”,“人工智能必定会把现有体系全部摧毁”,“新的AI市场必定建立在旧产业的废墟上”。而这些言论的出现,和我们日常最常听到的诸......