NO IMAGE

題目連結:poj 3783

題意分析:
經典題,紫書上的一道例題,4 2出了這道原題,我愣是以為是數學題,最後也沒做出來。題意是這樣的,給你N個雞蛋(硬度一樣),讓你測雞蛋的硬度,測量的方法就是從某棟M層的樓的某一層X上把雞蛋扔下來,如果雞蛋碎了,代表他的強度小於X;如果沒碎,則強度大於等於X。我們要做的就是不斷的從樓上把雞蛋扔下來,直到找到某一層樓X,從這一層樓扔下來雞蛋不碎掉,從X 1層扔下來雞蛋碎掉,那麼雞蛋的強度就是X。如果在M層扔下來雞蛋也不碎掉,那麼雞蛋的強度為M。問題是,用N個雞蛋最多需要幾步可以把硬度測出來(雞蛋碎掉就不能用了,而且必須測出來!)。
其實真正的問題是,對於硬度取值範圍為[0, M]的雞蛋,N次蛋碎的機會,最多需要多少步一定可以測出雞蛋的硬度。

解題思路:
一開始看懂題意之後,我馬上就想到了二分法,但是仔細一想並不對,如果雞蛋的數量足夠的話,二分法絕對是最快的,但是如果雞蛋不夠,就不太一樣了。如果第一次扔就碎了一個雞蛋,那麼剩下的雞蛋就只能從下往上測試,這樣2個雞蛋、100層樓的情況最多可能需要51步,然而測試樣例告訴我們,只要14步,當時想了足足有半個鍾才想到他可以用{ 14,13,12 …… }這樣的步長進行測試,這樣最多的測試數都是14次,這樣的原則確確實實可以解決2個雞蛋的問題,但是3個雞蛋就跪了,於是有了動態規劃演算法。
動態規劃演算法:
狀態:
dp[i][j]表示N=i,M=j時,最多需要多少次測試一定可以測出雞蛋的硬度。
狀態轉移方程:
如果我們一開始是在k層進行測試的,那麼如果雞蛋破碎了,我們的查詢範圍就變成k層以下的k-1層,當然此時雞蛋數減少了,所以最終的步數應該為dp[i-1][k-1] 1;另外一種情況是雞蛋沒有碎的情況,我們要找的範圍變成了k層以上的,所以最終需要dp[i][j-k] 1步。我們的目標就是要找到一個k,使得最壞情況下測試數最少,所以我們需要列舉k。程式碼如下:

    for(int i=2;i<=MAXN;i  )
{
for(int j=2;j<=MAXM;j  )
{
for(int k=1;k<j;k  )
{
dp[i][j]=min(dp[i][j],max(dp[i-1][k-1] 1,dp[i][j-k] 1));
}
}
}

初始狀態:
N=1時,測試數為M;M=1,測試數為1;M=0,測試數為0;

AC程式碼:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 55
#define MAXM 1005
using namespace std;
int n,m,dp[55][1005];
int main()
{
int T,t;
scanf("%d",&T);
memset(dp,INF,sizeof(dp));
for(int i=1;i<=MAXM;i  )
dp[1][i]=i;
for(int i=1;i<=MAXN;i  )
dp[i][1]=1,dp[i][0]=0;
for(int i=2;i<=MAXN;i  )
{
for(int j=2;j<=MAXM;j  )
{
for(int k=1;k<j;k  )
{
dp[i][j]=min(dp[i][j],max(dp[i-1][k-1] 1,dp[i][j-k] 1));
}
}
}   
while(T--)
{
scanf("%d %d %d",&t,&n,&m);
printf("%d %d\n",t,dp[n][m]);
}
return 0;
}

總結:
其實如果知道是用動態規劃做的話,狀態什麼的還是挺好想的,但是關鍵是想不到啊~~經驗不足真可怕,不過被時間複雜度嚇到也是一部分原因,居然沒想到離線。
1、多坐點題積累經驗吧;
2、不要被複雜度嚇到;
3、事實證明,智商很重要TAT