满血复活 - Programming版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

相关主题
● 请教算法：三等分石子
● 请教：Map reduce到底是什么啊 (转载)
● 请问各位工作的人，算法复杂度分析在工作中用的着吗？
● 最短路的算法复杂度问题
● 请问leetcode的使用方法？
● computer的历史就是不断地做出trade off. 每秒500万也一样。
● 太监尿遁了还能满血复活
● 我老人家从来说话算数
● 算法导论重点
● 如何理解回溯？

相关话题的讨论汇总
话题: 满血话题: 半血话题: 复活话题: 受伤话题: 机会

进入Programming版参与讨论

(共1页)

a*w
发帖数: 4495

有这么个回合制游戏，受伤若干次就挂了。系统随机生成一些满血复活和
半血复活的机会。
在挂掉时可以选择退回最多m步，选择一次满血复活把所有受伤次数清零，
或者半血复活，把受伤次数清一半。
在每n步之内，只能用一次复活，不管是满血还是半血。
最简单的解法是
回溯m步，如果有满血机会，用之；
若只有半血机会，向前搜索n步，如果没有用过满血，用半血；
如果啥机会都没有，只好挂了。
这个算法的复杂度是O(m) * O(n)。有没有更好的算法？
谢谢！

t****a
发帖数: 1212

题目很有趣，不过没有讲清楚：
1. 游戏的目标是什么？
2. 什么条件下会受伤？这是已知的吗？

(共1页)

进入Programming版参与讨论

相关主题
● 如何理解回溯？
● 关于内存泄漏
● 问个习惯问题
● 求助一个数据结构的求时间复杂度问题
● stl的nth_element的复杂度是不是O(N)？
● Θ(n)是什么意思？
● 这个算法的复杂度是多少？
● 解一道 GOOGLE 面试题 ...
● 请构造个数据结构，满足：
● 这个图问题的复杂度是多少呢

相关话题的讨论汇总
话题: 满血话题: 半血话题: 复活话题: 受伤话题: 机会

boards