openjudge 7627 雞蛋的硬度 DP

NO IMAGE

描述
最近XX公司舉辦了一個奇怪的比賽:雞蛋硬度之王爭霸賽。參賽者是來自世界各地的母雞,比賽的內容是看誰下的蛋最硬,更奇怪的是XX公司並不使用什麼精密儀器來測量蛋的硬度,他們採用了一種最老土的辦法–從高度扔雞蛋–來測試雞蛋的硬度,如果一次母雞下的蛋從高樓的第a層摔下來沒摔破,但是從a 1層摔下來時摔破了,那麼就說這隻母雞的雞蛋的硬度是a。你當然可以找出各種理由說明這種方法不科學,比如同一隻母雞下的蛋硬度可能不一樣等等,但是這不影響XX公司的爭霸賽,因為他們只是為了吸引大家的眼球,一個個雞蛋從100層的高樓上掉下來的時候,這情景還是能吸引很多人駐足觀看的,當然,XX公司也絕不會忘記在高樓上掛一條幅,寫上“XX公司”的字樣–這比賽不過是XX
公司的一個另類廣告而已。 勤于思考的小A總是能從一件事情中發現一個數學問題,這件事也不例外。“假如有很多同樣硬度的雞蛋,那麼我可以用二分的辦法用最少的次數測出雞蛋的硬度”,小A對自己的這個結論感到很滿意,不過很快麻煩來了,“但是,假如我的雞蛋不夠用呢,比如我只有1個雞蛋,那麼我就不得不從第1層樓開始一層一層的扔,最壞情況下我要扔100次。如果有2個雞蛋,那麼就從2層樓開始的地方扔……等等,不對,好像應該從1/3的地方開始扔才對,嗯,好像也不一定啊……3個雞蛋怎麼辦,4個,5個,更多呢……”,和往常一樣,小A又陷入了一個思維僵局,與其說他是勤于思考,不如說他是喜歡自找麻煩。
好吧,既然麻煩來了,就得有人去解決,小A的麻煩就靠你來解決了:)

輸入
輸入包括多組資料,每組資料一行,包含兩個正整數n和m(1<=n<=100,1<=m<=10),其中n表示樓的高度,m表示你現在擁有的雞蛋個數,這些雞蛋硬度相同(即它們從同樣高的地方掉下來要麼都摔碎要麼都不碎),並且小於等於n。你可以假定硬度為x的雞蛋從高度小於等於x的地方摔無論如何都不會碎(沒摔碎的雞蛋可以繼續使用),而只要從比x高的地方扔必然會碎。
對每組輸入資料,你可以假定雞蛋的硬度在0至n之間,即在n 1層扔雞蛋一定會碎。

輸出

對於每一組輸入,輸出一個整數,表示使用最優策略在最壞情況下所需要的扔雞蛋次數。

樣例輸入

100 1
100 2

樣例輸出

100
14

提示

最優策略指在最壞情況下所需要的扔雞蛋次數最少的策略。
如果只有一個雞蛋,你只能從第一層開始扔,在最壞的情況下,雞蛋的硬度是100,所以需要扔100次。如果採用其他策略,你可能無法測出雞蛋的硬度(比如你第一次在第二層的地方扔,結果碎了,這時你不能確定硬度是0還是1),即在最壞情況下你需要扔無限次,所以第一組資料的答案是100。

我們先從100層樓,2個雞蛋開始想:

假設我們得到答案一共需要試x次。
那麼第一個雞蛋從x層開始扔,如果碎了,第二個雞蛋從1~x-1層開始扔;如果沒碎,再從x x-1層開始扔。如果碎了,第二個雞蛋再從x 1~x x-2開始扔;否則,再從x x-1 x-2層開始扔。這樣一直推下去,假設第一個雞蛋一直沒碎,那麼我們會得到:
“X X−1 X−2 X−3 … 1 ≥ 100”
X≥14,也就是說我們在最壞情況下14次即可得到答案。

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

然後,我們擴充套件到n層樓,m個雞蛋:

用dp[i][j]來表示i層樓,用了j個雞蛋測試得到的最小步數。
如果雞蛋碎了,那麼可以從dp[i-1][j-1] 1得到答案;如果沒碎,那麼則可以從dp[n-i][j] 1得到答案。

真·DP:

#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;
}

偽·DP:

#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;
}