AcWing 1048. 鸡蛋的硬度
原题链接
中等
作者:
我要出去乱说
,
2021-02-01 23:13:47
,
所有人可见
,
阅读 362
方法一
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 11;
int n, m;
int f[N][M]; //N表示楼层数, M表示鸡蛋个数
int main()
{
while (cin >> n >> m)
{ //状态初始化
for (int i = 1; i <= n; i ++ ) f[i][1] = i; //高度为i只有一个鸡蛋要测i次
for (int i = 1; i <= m; i ++ ) f[1][i] = 1; //高度为一有i个鸡蛋只要测1次
for (int i = 2; i <= n; i ++ )
for (int j = 2; j <= m; j ++ )
{
f[i][j] = f[i][j - 1]; //第j个鸡蛋没用过
for (int k = 1; k <= i; k ++ )
//f[k-1][j-1]鸡蛋在第k层用,碎了; f[i-k][j]鸡蛋在第k层用,没碎
f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1);
}
cout << f[n][m] << endl;
}
return 0;
}
方法二
#include <cstdio>
const int N = 101, M = 11;
int n, m;
int f[N][N];
int main()
{
while (~scanf("%d%d", &n, &m))
{
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ ) f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1;
if (f[i][m] >= n)
{
printf("%d\n", i);
break;
}
}
}
return 0;
}