扔鸡蛋问题：f[i][j] 为 i 层楼、j 个蛋最坏情况的最少扔蛋次数，枚举首扔位置 x，碎则测下层段且蛋减一、不碎测上层段蛋不变，max 套 min，预计算全表后每组询问 O(1) 查表。
OJ: roj
题目 ID: 1300
难度:普及-
标签:动态规划区间DPpython
创建: 2026-09-30 03:53
更新: 2026-10-05 08:33
题目描述
楼高
输入包括多组数据，每组数据一行两个正整数 100 1 / 100 2，对应输出 100 / 14。
思路
一次扔蛋把问题切成两个更小的同类问题：在
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:53
# update_at: 2026-09-30 03:53
import sys
# 答案上界：100 层楼、1 个鸡蛋时最坏要扔 100 次
MAX_FLOORS = 100
MAX_EGGS = 10
def build_min_drops() -> list[list[int]]:
"""预计算 f[i][j]：i 层楼、j 个鸡蛋在最坏情况下的最少扔蛋次数。
f[i][1] = i（只有一个鸡蛋只能从低到高逐层试）；
j>=2 时在 x 层扔一次：碎了测 [1,x-1] 剩 j-1 个蛋，
没碎测 [x+1,i] 仍 j 个蛋，取两者最坏再 +1，x 取最小。
"""
f = [[0] * (MAX_EGGS + 1) for _ in range(MAX_FLOORS + 1)]
for floors in range(1, MAX_FLOORS + 1):
f[floors][1] = floors # 单蛋：逐层往上扔
for eggs in range(2, MAX_EGGS + 1):
# 枚举第一次扔的位置 x（1..floors），取最坏子问题较小者
f[floors][eggs] = 1 + min(
max(f[x - 1][eggs - 1], f[floors - x][eggs])
for x in range(1, floors + 1)
)
return f
def solve() -> None:
f = build_min_drops()
pairs = [list(map(int, line.split())) for line in sys.stdin if line.strip()]
print('\n'.join(str(f[n][m]) for n, m in pairs))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 08:33
* update_at: 2026-10-05 08:33
*/
// 扔鸡蛋：f[i][j] = i 层楼、j 个蛋，最坏情况下最少扔蛋次数
// 在 x 层扔一次：碎 -> 剩 x-1 层、j-1 个蛋；不碎 -> 剩 i-x 层、j 个蛋
// 对手挑更糟的分支（max），我方挑最优的首扔位置（min）
#include <cstdio>
typedef long long ll;
const int MAXN = 100; // 楼高上限
const int MAXM = 10; // 蛋数上限
ll f[MAXN + 5][MAXM + 5]; // f[楼层数][蛋数] = 最坏情况最少扔蛋次数
int main() {
// 按楼层数从小到大、蛋数从小到大填表，两个子分支都已算好
for (int j = 0; j <= MAXM; ++j) f[0][j] = 0; // 0 层楼不用扔
for (int i = 1; i <= MAXN; ++i) {
f[i][1] = i; // 单蛋只能从低到高逐层试
for (int j = 2; j <= MAXM; ++j) {
f[i][j] = MAXN; // 先放一个上界
for (int x = 1; x <= i; ++x) {
ll worst = f[x - 1][j - 1];
if (f[i - x][j] > worst) worst = f[i - x][j];
if (worst + 1 < f[i][j]) f[i][j] = worst + 1;
}
}
}
// 多组询问直接 O(1) 查表
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
printf("%lld\n", f[n][m]);
}
return 0;
}