题意（搬运了我们 $oj$ 的一题）
小明生产了 $m$ 个完全相同的玻璃杯，他想测试一下这些杯子的质量如何。他找到一个 $n$ 层楼的房子，每层楼等高。已知这种杯子恰好会从第 $x+1$ 层掉落时摔碎，在 $x$ 及其以下的楼层不会摔碎，在 $x+1$ 及其以上的楼层会摔碎，杯子摔碎之后即无法再次使用。他想知道，在最坏情况下精确测出 $x$ 需要扔几次杯子，$0 \leq x \leq n$。
数据范围：
| 测试点编号 | $n$ | $m$ | $T$ |
|---|---|---|---|
| $1$ | $\leq10$ | $\leq10$ | $\leq10$ |
| $2$ | $\leq5\times10^2$ | $\leq5\times10^2$ | $\leq 10^2$ |
| $3\sim5$ | $\leq 10^4$ | $\leq 10^4$ | $\leq 10^2$ |
| $6\sim7$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^4$ |
| $8\sim10$ | $\leq 10^{18}$ | $\leq 10^{18}$ | $\leq 2\times10^4$ |
Sol.
令 $f[i][j]$ 表示用 $i$ 个鸡蛋，检验硬度 $1\sim j$ 最少扔的次数。
$f[1][j]=j,f[i][1]=1$
$f[i][j]=min(max(f[i-1][k-1],f[i][j-k])+1$
效率 $O（n^2m）$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inf 1e9
using namespace std;
int n,m,f[15][105];
void dp(){
n=100,m=10;
for(int j=1;j<=n;j++)f[0][j]=inf;
for(int i=1;i<=m;i++){
f[i][1]=1;
for(int j=2;j<=n;j++){
int M=inf;
for(int k=1;k<=j;k++){
M=min(M,max(f[i-1][k-1],f[i][j-k])+1);
}
f[i][j]=M;
// cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
}
}
}
int main(){
dp();
while(~scanf("%d%d",&n,&m)){
printf("%d\n",f[m][n]);
}
return 0;
}
考虑研究下 dp 的结果
n=39, m=15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9
1 2 2 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6
数一数个数可以发现
1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10
1 2 4 7 11 16 22 29 8 0
1 2 4 8 15 26 42 2 0 0
1 2 4 8 16 31 38 0 0 0
1 2 4 8 16 32 37 0 0 0
有规律！ 于是就有了 $O(nm)$ 的递推算法
