poj1190 生日蛋糕
2024-09-08 11:09:21
题意:
要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。 设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时,要求Ri > Ri+1且Hi > Hi+1。 由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。 令Q = Sπ 请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。 (除Q外,以上所有数据皆为正整数)
思路:
深搜(枚举每一层的高度和半径)+剪枝
最优性剪枝:
搭建过程中预见到搭完后面积一定会超过目前最优表面积,则停止搭建。
可行性剪枝:
1.搭建过程中预见到再往上搭,高度已经无法安排,或者半径已经无法安排,则停止搭建。
2.搭建过程中发现还没搭的那些层的体积,最大也到不了还缺的体积,则停止搭建。(之前搭得太小)
3.搭建过程中发现还没搭的那些层的体积,一定会超过还缺的体积,则停止搭建。(之前搭得太大)
实现:
#include <iostream>
#include <cstdio>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
int min_now = INF;
int minV[];
int minA[]; int cal2(int a)
{
return a * a;
} int cal3(int a)
{
return a * a * a;
} int maxV(int r, int h, int rem)
{
int ans = ;
for (int i = ; i < rem; i++)
{
ans += r * r * h;
r--, h--;
}
return ans;
} void dfs(int cur, int v, int r, int h, int s)
{
if (s + minA[cur] >= min_now) //最优性剪枝
return;
if (r - < m - cur || h - < m - cur) //可行性剪枝1(之后无法安排)
return;
if (maxV(r - , h - , m - cur) < v) //可行性剪枝2(之前搭的太小)
return;
if (v < minV[cur]) //可行性剪枝3(之前搭得太大)
return;
if (cur == m)
{
if (v == )
{
if (s < min_now)
{
min_now = s;
}
}
return;
}
for (int i = h - ; i >= ; i--) // 枚举高度
{
for (int j = r - ; j >= ; j--) // 枚举半径
{
dfs(cur + , v - j * j * i, j, i, s + * j * i);
}
}
} int main()
{
cin >> n >> m;
minV[] = ( + m) * m / ;
minV[] = minV[] * minV[];
minA[] = m * (m + ) * ( * m + ) / ;
for (int i = ; i < m; i++)
{
minV[i] = minV[i - ] - cal3(m - i + );
minA[i] = minA[i - ] - * cal2(m - i + );
}
for (int i = sqrt(n) + ; i >= m; i--)
{
for (int j = n / i / i; j >= m; j--)
{
dfs(, n - i * i * j, i, j, i * i + * i * j);
}
}
if (min_now == INF)
puts("");
else
printf("%d\n", min_now);
return ;
}
最新文章
- SharePoint 2013 create workflow by SharePoint Designer 2013
- 潭州学院-JavaVIP的Javascript的高级进阶-KeKe老师
- java SpringUtil获取bean
- rails开发demo(一)搭建环境
- Cisco(思科)路由器静态路由的配置
- Hibernate学习之关系映射(转)
- 再造 “手机QQ” 侧滑菜单(三)——视图联动
- 我的开发环境搭建(ubuntu菜鸟)
- java中类的三大特征之多态
- Java I/O输入输出流
- 在Java中进行序列化和反序列化
- CentOS7安装k8s
- rsync排除多个文件实现同步
- 帝国cms内容关键字自动加链接且设置内容关键字只替换一次
- learning ddr3 protocol
- 通过httpclient3实现文件下载以及获取文件下载名称
- 2.7 usb摄像头之usb摄像头描述符打印
- PCL学习笔记二:Registration (ICP算法)
- windows 搭建 subversion+TortoiseSVN
- 温故而知新-strtok函数
热门文章
- spring boot---WebFilter注解 实现自定义登录过滤器
- vue中导出Excel表格
- react native与原生的交互
- SDUT OJ 图练习-BFS-从起点到目标点的最短步数 (vector二维数组模拟邻接表+bfs , *【模板】 )
- YTU 2577: 小数计算——结构体
- fullcalendar小结
- php连接数据库步骤
- HihoCoder1705: 座位问题(STL)
- web.xml配置之<;context-param>;
- 斯坦福CS231n—深度学习与计算机视觉----学习笔记 课时5