满血复活 - Programming版

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

相关主题
● 请教算法：三等分石子	● 算法导论重点
● 请教：Map reduce到底是什么啊 (转载)	● 如何理解回溯？
● 请问各位工作的人，算法复杂度分析在工作中用的着吗？	● 关于内存泄漏
● 最短路的算法复杂度问题	● 问个习惯问题
● 请问leetcode的使用方法？	● 求助一个数据结构的求时间复杂度问题
● computer的历史就是不断地做出trade off. 每秒500万也一样。	● stl的nth_element的复杂度是不是O(N)？
● 太监尿遁了还能满血复活	● Θ(n)是什么意思？
● 我老人家从来说话算数	● 这个算法的复杂度是多少？

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

进入Programming版参与讨论

(共1页)

a*w
发帖数: 4495

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

t****a
发帖数: 1212

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

(共1页)

进入Programming版参与讨论

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

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

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天