題目：測試次數(shù)
星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機！
? ? ? ?各大廠商也就紛紛推出各種耐摔型手機。x星球的質(zhì)監(jiān)局規(guī)定了手機必須經(jīng)過耐摔測試，并且評定出一個耐摔指數(shù)來，之后才允許上市流通。
? ? ? ? x星球有很多高聳入云的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當(dāng)于我們的2樓。?
? ? ? ? 如果手機從第7層扔下去沒摔壞，但第8層摔壞了，則手機耐摔指數(shù)=7。####特別地，如果手機從第1層扔下去就壞了，則耐摔指數(shù)=0。
? ? ? ? 如果到了塔的最高層第n層扔沒摔壞，則耐摔指數(shù)=n?
? ? ? ? 為了減少測試次數(shù)，從每個廠家抽樣3部手機參加測試。
? ? ? ?某次測試的塔高為1000層，如果我們總是采用最佳策略，在最壞的運氣下最多需要測試多少次才能確定手機的耐摔指數(shù)呢？
? ? ? ? 請?zhí)顚戇@個最多測試次數(shù)。
? ? ? ? 注意：需要填寫的是一個整數(shù)，不要填寫任何多余內(nèi)容。
看到題目的第一眼??，我的直觀感受就是二分法哇，太簡單了，撿到了撿到了。
后來，考完很久以后，我又重新刷題，感覺不對，應(yīng)該不是這么簡單的。應(yīng)該是DP動態(tài)規(guī)劃！
題解：
1、理解題意：?
? ? ? ? 已知n是耐摔指數(shù)，有3部手機，求解最壞情況下至少摔K次。
? ? ? ? 在此題，n可能是區(qū)間[0,1000]上的任意一個數(shù)字，那么我們保證在K次里，不論n = 0，1，... ，1000 中的哪個數(shù)字，我們都能準(zhǔn)確確定n的值。
2、抽象成模型：
? ? ? ? ?抽象成一根數(shù)軸，n在區(qū)間[0，1000]
? ? ? ? 我設(shè)dp[ind][cnt]為 ? ?ind為區(qū)間長度，cnt部手機，數(shù)組dp記錄確定n需要的局部最少次數(shù)。
? ? ? ? ?如果只有 1 部手機，那就只能從小到大，一次一次實驗。直測試出n。
? ? ? ? ?如果有 2 部手機，我們開始分塊，
? ? ? ? ?分成1：999，2:998，3:997，...... 諸如此類 所以我也不知道哪種分塊最優(yōu)啊，當(dāng)然是暴力遍歷一遍啦！
? ? ? ? 這時候狀態(tài)就可以轉(zhuǎn)化成：到底碎不碎了？
? ? ? ? 如果在K層碎了，問題就等價成：搜索區(qū)間 [0,k-1]的次數(shù) + 1；
? ? ? ? 如果在K層沒有碎，問題就等價成：搜索區(qū)間[k+1，1000]的次數(shù) + 1； ?
思考一下，確定n[k,1000] 所需要的次數(shù) ? 是不是 ?等價于 ?確定n
[0,1000 - k] 所需要的次數(shù)！因為區(qū)間長度一致哇！
? ? ? ? ?如果有cnt部手機，ind層時，
? ? ? ? ?dp[ind][cnt] = Min(dp[ind-1][cnt]+1 , 1+Max( dp[k - 1][cnt - 1] , dp[ ind-k ][ cnt ] ) ?)
解釋一下 ?用Max函數(shù)和Min函數(shù)：
我們本意是寫一個算法，實現(xiàn)對n是任何可能值的求解。
假設(shè)層數(shù)是6，2部手機，看圖解：
結(jié)論：題目實際是求全局最優(yōu)解——常用方法DP！
DP：全局最優(yōu)——>局部最優(yōu)——>求動態(tài)轉(zhuǎn)移方程
就是用動態(tài)規(guī)劃的思想，去走遍所有所可能的情況，通過條件限制，求最小次數(shù)啦。
Max：最壞情況的判斷，n=2是最好情況，可是如果這些手機耐摔指數(shù)
n=0，1，2，3，4，5，6呢！
Min：最少次數(shù)的選擇，情況雖然不妙！但是我們可以盡量少花力氣去摔手機哇！
選出確定dp[ ind ][ cnt ]需要的最小次數(shù)。
狀態(tài)方程就這么總結(jié)出來啦?。?！
?dp[ind][cnt] = Min( dp[ind-1][cnt]+1 , 1+Max( dp[k - 1][cnt - 1] , dp[ ind-k ][ cnt ] ) ?)
3、代碼實現(xiàn)：
#include
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
intdp[1002][5];
intmain(){
? ? for(inti =1; i <=1000; i++){//初始化邊界
? ? ? ? dp[i][1] = i;
? ? }
? ? for(intcnt =2; cnt <=3; cnt++){
? ? ? ? for(intind =1; ind <=1000; ind++){
? ? ? ? ? ? dp[ind][cnt] =dp[ind-1][cnt] +1;
? ? ? ? ? ? for(intk =2; k <= ind; k++){
? ? ? ? ? ? ? ? dp[ind][cnt] =Min(dp[ind][cnt],1+Max(dp[k-1][cnt-1],dp[ind-k][cnt]));
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? printf("%d\n",dp[1000][3]);
? ? return 0;
}
第一次寫題解，寫得不好的地方請大家指出。幫我進(jìn)步?。ㄆ鋵嵎艌D是因為我不會換行）
