主题:
动态规划及优化

题目:
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表示勾选):

• 习题
• OT

推荐理由:
从 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