题目:
There is a tower of n floors, and an egg dropper with m ideal eggs. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor n or above, and will have no damage whatsoever if it is dropped from floor n - 1 or below. The problem is to find a strategy such that the egg dropper can determine the floor n* in as few egg drops as possible.
hengxin
commented
5 years ago
主题: 动态规划及优化
题目: There is a tower of n floors, and an egg dropper with m ideal eggs. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor n or above, and will have no damage whatsoever if it is dropped from floor n - 1 or below. The problem is to find a strategy such that the egg dropper can determine the floor n* in as few egg drops as possible.
习题 还是 OT (在
[]中填入x表示勾选):推荐理由: 从 O(n\^2m) 的 DP 可以优化到 O(sqrt(n))，换一种思路又可以优化到 O(lgn)。 有点复杂但很有趣。
题解: Egg Dropping _ Brilliant Math & Science Wiki 优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化（IOI2004 国家集训队论文 朱晨光）
参考资料: https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle