# openjudge 7627 雞蛋的硬度 DP

100 1
100 2

100
14

“X X−1 X−2 X−3 … 1 ≥ 100”
X≥14，也就是說我們在最壞情況下14次即可得到答案。

PS:至於為什麼一開始要從x層開始扔，因為我們要保證最壞情況下的答案一直是x啊

``````#include <iostream>
#include <cstdio>
using namespace std;
int dp[110][20];
int main()
{
for(int i = 1; i <= 100; i  )
for(int j = 1; j <= 10; j  )
dp[i][j] = i;
for(int i = 1; i <= 100; i  )
for(int j = 1; j <= i; j  )
for(int k = 2; k <= 10; k  )
dp[i][k] = min(dp[i][k], 1   max(dp[j - 1][k - 1], dp[i - j][k]));
int n, m;
while(scanf("%d%d", &n, &m) != EOF)
{
printf("%d\n", dp[n][m]);
}
return 0;
}``````

``````#include <iostream>
#include <cstdio>
using namespace std;
const int INF = 2147483647;
int f[200][50];
int dp(int n, int m)
{
if(f[n][m] < INF) return f[n][m];
if(n == 1) return f[n][m] = 1;
if(n == 0) return f[n][m] = 0;
if(m == 1) return f[n][m] = n;
if(m == 0) return f[n][m] = 0;
for(int i = 1; i <= n; i  )
f[n][m] = min(f[n][m], 1   max(dp(i - 1, m - 1), dp(n - i, m)));
return f[n][m];
}
int main()
{
for(int i = 1; i <= 100; i  )
for(int j = 0; j <= 10; j  )
f[i][j] = INF;
int n, m;
while(scanf("%d%d", &n, &m) != EOF)
{
printf("%d\n", dp(n, m));
}
return 0;
}``````