先想一个简单问题:只有两个鸡蛋的问题
-
两个软硬一样但未知的鸡蛋。有座100层的建筑,要你⽤用这两个鸡蛋确定 哪一层是鸡蛋可以安全落下的最⾼高位置。可以摔碎两个鸡蛋。
-
这是典型的动态规划问题。假设$f[n]$表示从n层楼找到摔鸡蛋不不碎安全位置的最少判断次数。假设第⼀个鸡蛋第一次从第i层扔下,如果碎了了,就剩⼀个鸡蛋,为确定下⾯面楼层中的安全位置,必须从第⼀层挨着试,还需 要$i-1$次;如果不不碎的话,上⾯面还有$n-i$层,剩下两个鸡蛋,还需要$f[n-i]$次 (⼦子问题,n层楼的上n-i层需要的最少判断次数和n-i层楼需要的最少判断 次数其实是⼀样的)。因此,最坏情况下还需要判断max(i-1,f[n-i])次。
-
状态转移⽅方程:$$f[n] = min{1+max(i-1,f[n-i]) | i=1…n } $$
-
初始条件: f[0]=0(或f[1]=1)
推广成n层楼,m个鸡蛋
-
还是动态规划。假设f[n,m]表示n层楼、m个鸡蛋时找到摔鸡 蛋不不碎的最少判断次数。则⼀个鸡蛋从第i层扔下,如果碎 了了,还剩m-1个鸡蛋,为确定下⾯面楼层中的安全位置,还需 要$f[i-1,m-1]$次(⼦子问题);不不碎的话,上⾯面还有n-i层,还 需要$f[n-i,m]$次(⼦子问题,n层楼的上的n-i层需要的最少判断次数和n-i层楼需要的最少判断次数其实是⼀样的)。
-
状态转移⽅方程:$$f[n,m] = min{1+max(f[i-1,m-1], f[n-i,m]) | i= 1..n} $$
-
初始条件:f[i,0]=0(或f[i,1]=i),对所有i
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int f[102][12];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = 1; i <= 10; ++i)
{
for (int j = 1; j <= 100; ++j)
{
if (i == 1)
f[j][i] = j;
else
{
f[j][i] = 1e8;
for (int k = 1; k <= j; ++k)
{
f[j][i] = min(f[j][i], max(f[k - 1][i - 1], f[j - k][i]) + 1);
}
}
}
}
while (cin >> n >> m)
{
cout << f[n][m] << endl;
}
return 0;
}
感谢大佬,你的题解最清晰,豁然开朗~