DFS,BFS--Balloons

这篇文章，是我第一篇文。有没说清、说的不好的请评论指出，谢谢(* ॑꒳ ॑* )⋆*

:

DFS,BFS--Balloons
DFS,BFS--Balloons DFS,BFS--Balloons

---

题目链接

这个题可以发现其是一个枚举所有种情况，然后找出最优解。枚举所有情况其实就是一个DFS模板题。每个志愿者都由三种因素构成:One number of balloons generated    ,  Two  志愿者工作后的休息时间  ,Three  当你遍历到某个志愿者时可能他还处于休息时间所以你要等到他休息时间的结束，这是因为你要遍历所有情况，并且这种情况是有可能产生最优解的。那就用一个结构数组存储志愿者了。

题目密码:hnustacm

代码

提交结果

DFS,BFS--Balloons

这个题有一个坑点，就是题目对志愿者个数约束为1~10，但测试数据是100左右。

当某一个志愿者是 0  X ，就是说他在一分钟中产生了O个气球。如果不对这种数据处理的话，你会发现程序的结束条件对于有的情况无法控制结束。。。并且这种志愿者是占用了时间而没有对气球数有贡献。显然会有几种最优解里不存在这种志愿者(想想就知道了)，这点我的代码里有体现的。

当程序遍历完某个志愿者时，花费了时间。所以其他志愿者的cd时间也就减少了，但只能小到0。那个志愿者也会有变化。

其实就是个模拟过程。

当所有志愿者都是O X的话，这个题是无解。所以其实检测数据是不会这种的。

DFS：深度优先搜索，利用栈这种数据结构来实现（利用递归便于实现，但是效率较低），找到的第一个解不一定是最优解，只是先序遍历最早的可行解，然后回溯，再遍历直至结束。

如果不懂的话，可以看下这个，挺不错的。

DFS,BFS < 1 >

DFS,BFS < 2 >

转载注明出处

明天会更新最小生成树和最短路径的文章

---