蜗牛の狂奔笔记
对于蜗牛来说,狂奔虽不代表极速,但展现的却是一种拼尽全力的姿态........
pku 1190
2009年8月6日 星期四
题目链接:
PKU 1190 生日蛋糕
分类:一道DFS
题目分析与算法原型:
因为题目给的数据范围不大,蛋糕总共不会超过20层,所以可以采用DFS解决,先从最底层即m层开始往上枚举,每上一层,层数减1,直到最顶层,对于每层,枚举其最大的可能半径到最小的可能半径 ,以及对应的最大的高度到最小的高度,然后DFS。
注意这题可以做一些减枝,因为题目说每层蛋糕的半径和高度都比下面层的蛋糕的小,就是说,至少小1,那么,可以发现如果当前是第x层,那么该层的蛋糕的高度和半径至少是x(假设最顶层的半径和高度都取最小,为1)然后可以根据当前的累积面积和剩余的体积可以估计出此层开始递归计算出的最小面积和所剩的体积,然后对比从剩余的体积和最小面积,如果不满足一定的约束即return ,这样可以减一些时间的开销.
1
#include
<
stdio.h
>
2
#include
<
math.h
>
3
#define
max 0x7fffffff
4
int
mins[
25
],minv[
25
],n,m,ms;
5
6
//
当前层数,下面那层的半径,高度,剩余体积,所用的面积
7
void
dfs(
int
cur_f,
int
last_r,
int
last_h,
int
leave_v,
int
sum_s)
//
从最底层n开始计算到1层
8
{
9
int
i,j,max_h;
10
if
(sum_s
+
mins[cur_f]
>=
ms
||
leave_v
<
minv[cur_f])
return
;
11
//
估算所用的最小面积比现有的最小面积大,或者所用的体积不满足要求
12
if
(cur_f
==
0
)
13
{
14
if
(leave_v
==
0
&&
ms
>
sum_s)ms
=
sum_s;
15
return
;
16
}
17
for
(i
=
last_r
-
1
;i
>=
cur_f;i
--
)
18
{
19
int
kk
=
(
int
)((leave_v
-
minv[cur_f
-
1
])
/
(
double
)(i
*
i));
20
max_h
=
kk
<
(last_h
-
1
)
?
kk :(last_h
-
1
);
21
for
(j
=
max_h;j
>=
cur_f;j
--
)
22
{
23
if
(
2
*
(leave_v
-
i
*
i
*
j)
/
i
+
sum_s
+
2
*
i
*
j
>=
ms)
continue
;
24
//
若估算所用的最小面积比现有的最小面积大则忽略该次枚举
25
int
v
=
i
*
i
*
j,s
=
2
*
i
*
j;
26
if
(cur_f
==
m)s
+=
i
*
i;
27
dfs(cur_f
-
1
,i,j,leave_v
-
v,sum_s
+
s);
28
}
29
}
30
}
31
32
int
main()
33
{
34
int
i;
35
mins[
0
]
=
0
;
36
minv[
0
]
=
0
;
37
for
(i
=
1
;i
<=
20
;i
++
)
//mins[i]和minv[i]代表从第一层开始累积到第i层,蛋糕的最小可能面积和体积
38
{
39
mins[i]
=
mins[i
-
1
]
+
2
*
i
*
i;
40
minv[i]
=
minv[i
-
1
]
+
i
*
i
*
i;
41
}
42
while
(scanf(
"
%d%d
"
,
&
n,
&
m)
!=
EOF)
43
{
44
ms
=
max;
45
int
beg
=
(
int
)sqrt((
double
)n)
+
1
;
46
dfs(m,beg,beg,n,
0
);
47
if
(ms
!=
max)printf(
"
%d
"
,ms);
48
else
printf(
"
0\n
"
);
49
}
50
return
1
;
51
}
52
posted on 2009-08-07 00:04
蜗牛也Coding
阅读(442)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 蜗牛也Coding
<
2009年8月
>
日
一
二
三
四
五
六
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 78
文章 - 0
评论 - 96
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔档案
(78)
2011年7月 (1)
2011年4月 (1)
2010年11月 (4)
2010年10月 (4)
2010年9月 (2)
2010年8月 (7)
2010年3月 (1)
2010年2月 (5)
2009年12月 (2)
2009年10月 (1)
2009年9月 (1)
2009年8月 (16)
2009年7月 (31)
2009年6月 (2)
搜索
积分与排名
积分 - 91683
排名 - 259
最新评论
1. re: 关于 OpenGl
太谢谢了。
--袁锋
2. re: 关于 OpenGl
太感谢!
--芙
3. re: 关于MAC系统win 7虚拟机不能上网的问题[未登录]
.vmx文件在哪里?
--a
4. re: MFC中如何将 CFormView放置到一个CDockablePane中
注释掉的创建部分,指针调用
为何不用友元类声明下,就可以用了的。CreateOne,有点绕。
感谢博主分享。
--ren
5. re: 关于 OpenGl
非常感谢~~
--无叶莲
阅读排行榜
1. pragma comment的使用(转)(17177)
2. MFC中如何将 CFormView放置到一个CDockablePane中(8154)
3. (转)关于OpenGL的安装(4821)
4. 关于 OpenGl(4391)
5. VC 界面窗口,静态分割后如何锁定分隔条或限制分隔条的移动范围(4272)
评论排行榜
1. 据说是来自chrome的代码里的一个模板(13)
2. 关于 OpenGl(10)
3. Visual Studio 历史简介(转)(6)
4. pku 1200(6)
5. 推免--北航(5)