題目（直接貼了）

最近XX公司舉辦了一個(gè)奇怪的比賽：雞蛋硬度之王爭霸賽。參賽者是來自世 界各地的母雞，比賽的內(nèi)容是看誰下的蛋最硬，更奇怪的是XX公司并不使用什么精密儀器來測量蛋的硬度，他們采用了一種最老土的辦法–從高度扔雞蛋–來 測試雞蛋的硬度，如果一次母雞下的蛋從高樓的第a層摔下來沒摔破，但是從a+1層摔下來時(shí)摔破了，那么就說這只母雞的雞蛋的硬度是a。你當(dāng)然可以找出各種 理由說明這種方法不科學(xué)，比如同一只母雞下的蛋硬度可能不一樣等等，但是這不影響XX公司的爭霸賽，因?yàn)樗麄冎皇菫榱宋蠹业难矍?#xff0c;一個(gè)個(gè)雞蛋從100 層的高樓上掉下來的時(shí)候，這情景還是能吸引很多人駐足觀看的，當(dāng)然，XX公司也絕不會(huì)忘記在高樓上掛一條幅，寫上“XX公司”的字樣–這比賽不過是XX 公司的一個(gè)另類廣告而已。
勤于思考的小A總是能從一件事情中發(fā)現(xiàn)一個(gè)數(shù)學(xué)問題，這件事也不例外。“假如有很多同樣硬度的雞蛋，那么我可以用二分的辦法用最少的次數(shù)測出雞蛋 的硬度”，小A對(duì)自己的這個(gè)結(jié)論感到很滿意，不過很快麻煩來了，“但是，假如我的雞蛋不夠用呢，比如我只有1個(gè)雞蛋，那么我就不得不從第1層樓開始一層一 層的扔，最壞情況下我要扔100次。如果有2個(gè)雞蛋，那么就從2層樓開始的地方扔……等等，不對(duì)，好像應(yīng)該從1/3的地方開始扔才對(duì)，嗯，好像也不一定 啊……3個(gè)雞蛋怎么辦，4個(gè)，5個(gè)，更多呢……”，和往常一樣，小A又陷入了一個(gè)思維僵局，與其說他是勤于思考，不如說他是喜歡自找麻煩。
好吧，既然麻煩來了，就得有人去解決，小A的麻煩就靠你來解決了：）

---

輸入

100 1
100 2

輸出

100
14

樣例解釋

最優(yōu)策略指在最壞情況下所需要的扔雞蛋次數(shù)最少的策略。
如果只有一個(gè)雞蛋，你只能從第一層開始扔，在最壞的情況下，雞蛋的硬度是100，所以需要扔100次。如果采用其他策略，你可能無法測出雞蛋的硬度(比如你第一次在第二層的地方扔,結(jié)果碎了,這時(shí)你不能確定硬度是0還是1)，即在最壞情況下你需要扔無限次，所以第一組數(shù)據(jù)的答案是100。
第二組樣例不解釋

---

解題思路

我們用f[i][j]表示從第i層用j個(gè)雞蛋的最壞情況中的最優(yōu)解，然后我們可以用碎了或沒有碎的最大值來表示
最壞的情況，然后循環(huán)一下，求在最壞情況中的最優(yōu)解。
動(dòng)態(tài)轉(zhuǎn)移方程：
f[i][j]=min(max(f[i-1][k-1],f[i][j-k])+1)

---

代碼

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[11][101],n,m; int main() {memset(f,127/3,sizeof(f));//賦值一個(gè)很大很大的整數(shù)for (int i=1;i<=100;i++) f[1][i]=i;//一個(gè)雞蛋只能一樓一樓扔for (int i=0;i<=10;i++) f[i][0]=0;//0層樓不用扔for (int i=2;i<=10;i++)for (int j=1;j<=100;j++){for (int k=1;k<=j;k++) f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);//動(dòng)態(tài)轉(zhuǎn)移}while (scanf("%d%d",&n,&m)==2){printf("%d\n",f[m][n]);//輸出} }

總結(jié)

以上是生活随笔為你收集整理的OJ7627-鸡蛋的硬度【各种dp之4】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。