题目：鸡蛋掉落（Egg Dropping）问题的变种——带楼层限制的鸡蛋掉落
题目描述
你面前有一栋从 1 到 \(F\) 层的高楼。
你有 \(E\) 个完全相同的鸡蛋，并希望确定一个“临界楼层” \(X\)——在这层楼扔下鸡蛋鸡蛋不会碎，但在 \(X+1\) 层或更高层扔下鸡蛋鸡蛋就会碎。
你可以从某一层扔下一个鸡蛋，并观察结果（碎或不碎）。
但有一个额外限制：你最多只能扔 \(M\) 次鸡蛋（总次数限制）。
你的目标是：在最多扔 \(M\) 次的条件下，保证能找到临界楼层。
请问：在给定 \(E, M, F\) 时，是否可能保证找到临界楼层？如果可能，输出最少所需的测试方案下能支持的最大 \(F\) 值；如果不可能，输出 -1。
注意：这是一个“决策”与“优化”结合的问题，更常见的表述是：
- 给定 \(E\) 个鸡蛋和 \(M\) 次扔鸡蛋机会，能确定的最大楼层数 \(F\) 是多少？
- 反过来，如果 \(F\) 已知，问最少需要多少次扔鸡蛋才能保证找出 \(X\)？
本题是给定 \(E, M, F\)，判断是否可行（即 \(F \leq dp[E][M]\)）。
问题抽象
设 \(dp[e][m]\) 表示有 \(e\) 个鸡蛋，最多允许扔 \(m\) 次，在最坏情况下能确定的最大楼层数。
我们要求的就是 \(dp[E][M] \geq F\) 是否成立。
解题思路
1. 基本想法
如果只有一个鸡蛋（\(e=1\)），那么只能从第 1 层开始逐层往上试，最坏情况需要试到第 \(F\) 层，所以最多能确定的楼层数 = \(m\)（因为最多允许扔 \(m\) 次）。
即：
\[dp[1][m] = m \]
如果没有扔鸡蛋的次数（\(m=0\)），则无法确定任何楼层：
\[dp[e][0] = 0 \]
2. 状态转移
假设第一次扔鸡蛋在第 \(k\) 层：
- 如果鸡蛋碎了：则临界楼层在 \(1\) 到 \(k-1\) 层之间，鸡蛋数变为 \(e-1\)，剩余次数为 \(m-1\)，能确定的楼层数为 \(dp[e-1][m-1]\)。
- 如果鸡蛋没碎：则临界楼层在 \(k+1\) 到某个更高层之间，鸡蛋数仍为 \(e\)，剩余次数为 \(m-1\)，能确定的楼层数为 \(dp[e][m-1]\)。
因为要保证最坏情况下也能确定，所以我们能确定的楼层数为：
\[1 + dp[e-1][m-1] + dp[e][m-1] \]
其中：
- 1 表示当前测试的第 \(k\) 层。
- 如果鸡蛋碎了，可以确定下面的 \(dp[e-1][m-1]\) 层。
- 如果鸡蛋没碎，可以确定上面的 \(dp[e][m-1]\) 层。
我们要最大化能确定的总楼层数，所以最优的 \(k\) 就是使这两部分平衡，但动态规划中我们不需要枚举 \(k\)，因为公式已经给出：
\[dp[e][m] = 1 + dp[e-1][m-1] + dp[e][m-1] \]
这个公式的直观理解：第一次扔在第 \(dp[e-1][m-1]+1\) 层是最优的，所以直接相加即可。
3. 初始化
- \(dp[e][0] = 0\)（没有次数，无法确定任何楼层）。
- \(dp[1][m] = m\)（只有一个鸡蛋，只能线性探测）。
4. 计算顺序
按 \(m\) 从 1 到 \(M\)，\(e\) 从 1 到 \(E\) 递推。
注意：如果 \(E\) 很大，但 \(M\) 很小，能确定的楼层数是有限的。实际中，\(dp[e][m]\) 可能增长非常快（类似组合数求和）。
5. 判断可行性
计算 \(dp[E][M]\)，如果 \(dp[E][M] \geq F\)，则可行，否则不可行。
举例说明
例：\(E=2, M=6, F=100\)
初始化：
\[dp[1][m] = m \]
\[ dp[e][0] = 0 \]
递推：
- \(m=1\)：
\(dp[2][1] = 1 + dp[1][0] + dp[2][0] = 1 + 0 + 0 = 1\) - \(m=2\)：
\(dp[2][2] = 1 + dp[1][1] + dp[2][1] = 1 + 1 + 1 = 3\) - \(m=3\)：
\(dp[2][3] = 1 + dp[1][2] + dp[2][2] = 1 + 2 + 3 = 6\) - \(m=4\)：
\(dp[2][4] = 1 + dp[1][3] + dp[2][3] = 1 + 3 + 6 = 10\) - \(m=5\)：
\(dp[2][5] = 1 + dp[1][4] + dp[2][4] = 1 + 4 + 10 = 15\) - \(m=6\)：
\(dp[2][6] = 1 + dp[1][5] + dp[2][5] = 1 + 5 + 15 = 21\)
结果：\(dp[2][6] = 21 < 100\)，所以用 2 个鸡蛋、最多扔 6 次，无法保证在 100 层楼中确定临界楼层。
算法复杂度
- 时间复杂度：\(O(E \times M)\)
- 空间复杂度：\(O(E \times M)\)，可优化到 \(O(E)\)
边界情况
- 如果 \(E=0\) 或 \(M=0\)，无法确定任何楼层（除非 \(F=0\)）。
- 如果 \(F=0\) 或 \(F=1\)，总可行（不需要扔鸡蛋或只需一次）。
- 注意数值溢出：\(dp[e][m]\) 可能增长很快，超过普通整数范围，需用 64 位整数。
核心思想总结
这个问题是经典的“鸡蛋掉落”问题的变种，限制了最大扔鸡蛋次数 \(M\)。
通过定义 \(dp[e][m]\) 为最大可确定的楼层数，利用“碎”与“不碎”两种情况的子问题相加再加 1 来递推，可以高效判断可行性。