鸡蛋掉落问题C++带阿米
时间: 2023-07-11 14:10:09 浏览: 49
以下是带有注释的鸡蛋掉落问题的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005;
int n, k;
int dp[N][N]; // dp[i][j] 表示 i 个鸡蛋在 j 层楼最多可以尝试多少次
int main()
{
cin >> n >> k;
// 当只有一颗鸡蛋时,最多需要尝试 k 次
for (int j = 1; j <= k; j ++ ) dp[1][j] = j;
// 当只有一层楼时,最多只需要尝试一次
for (int i = 1; i <= n; i ++ ) dp[i][1] = 1;
// 递推公式
for (int i = 2; i <= n; i ++ )
for (int j = 2; j <= k; j ++ )
{
dp[i][j] = 0x3f3f3f3f; // 初始化为一个很大的数
for (int x = 1; x <= j; x ++ )
// 在 x 层楼扔鸡蛋,有两种情况:
// 1. 鸡蛋碎了,需要在 x 层以下的楼层继续寻找
// 2. 鸡蛋没碎,需要在 x 层以上的楼层继续寻找
// max(dp[i-1][x-1], dp[i][j-x]) 表示这两种情况的最大值
// 因为我们需要找到最坏情况下的最少尝试次数
// 加 1 是因为我们需要在 x 层楼扔鸡蛋一次
dp[i][j] = min(dp[i][j], max(dp[i-1][x-1], dp[i][j-x]) + 1);
}
// 输出 n 个鸡蛋在 k 层楼最少需要尝试的次数
cout << dp[n][k] << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)