【UVA1009/WF2002A】 Balloons in a Box(枚举)

27
Aug

【UVA1009/WF2002A】 Balloons in a Box(枚举)

最近开始读刘汝佳的黑书,这是书里的第一题。这道题的思路还是比较简单的,但是在实际的比赛中如何快速想到使用枚举,却值得思考。另外这题也有一些小的坑点,所以还是WA了几发才过,这里也简单描述一下。

题面描述

给定一个空间中的盒子,并给定N(N<=6)个在盒子中的点。在每个点都放上气球,气球初始没有体积。按一定顺序吹气球,当且仅当此气球碰到盒子的边界或其他气球时停止扩张。求在所有吹气球的顺序中,使得最终气球总体积最大的值。输出此时盒子的剩余体积,约到整数输出。

解题思路

由于数据量很小(N<=6),已知其可能情况的规模N!的值不会超过6!=720,且所有操作的顺序具有后继性,因此可以考虑直接用枚举法搜索全部结果。

代码编写

首先预处理好盒子的体积,每个点到盒子边界的最近距离,以及每两个点之间的距离,可以直接采用一个二维数组存储。枚举的过程选择采用BFS来写,代码和思维量较小。在对每一个状态的储存最关键需要的是当前每个点处气球的半径大小,还没有吹则用-1表示,每次选择一个点进行扩展,直至遍历完整棵树。
特别于这道题而言,需要注意其结果在cout下输出可能会出现科学记数法表示的问题,需要使用printf输出。另外每组输出后需接两个换行符。

AC代码
代码地址:https://paste.ubuntu.com/25426113/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论