x星球的居民脾氣不太好，但好在他們生氣的時候唯一的例外舉動是：摔手機，
各大廠商也就紛紛推出各種耐摔型手機，x星球的質監局規定了手機必須經過耐摔測驗，并且評定出一個耐摔指數來，之后才允許上市流通，
x星球有很多高聳入云的高塔，剛好可以用來做耐摔測驗，塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當于我們的2樓，
如果手機從第7層扔下去沒摔壞，但第8層摔壞了，則手機耐摔指數=7，
特別地，如果手機從第1層扔下去就壞了，則耐摔指數=0，
如果到了塔的最高層第n層扔沒摔壞，則耐摔指數=n
為了減少測驗次數，從每個廠家抽樣3部手機參加測驗，
某次測驗的塔高為1000層，如果我們總是采用最佳策略，在最壞的運氣下最多需要測驗多少次才能確定手機的耐摔指數呢？
請填寫這個最多測驗次數，
題目有兩個關鍵點，一個是最壞運氣，摔死了3部手機并且測驗到最后一次才能測出耐摔指數所需要測驗次數，即一個最多的測驗次數，無論手機的耐摔指數是多少，總能在這個測驗次數前 找到該手機的耐摔指數 ，第二個就是最佳策略，我們沒有辦法決定手機的耐摔指數，但是可以決定從哪一層開始摔，題目就是要我們求一個從各層開始都摔一次，且在各層測驗次數最大的情況下，找到一個最小的值
1.摔壞了，那么可以確定摔壞的樓層應該是第1層到第k層（n >= k），共k層，
2.沒摔壞，可以確定摔壞的樓層應該是第k+1層到第j層，共j-k層，
dp[i][j]=max(dp[i-1][k-1],dp[i][j-k])+1,k∈[1,j-1]（這里取max是因為要滿足最壞運氣）
一開始在給dp陣列初始化的時候，可以全部初始化為它的最壞情況，j層樓的最壞測驗次數是j次，就是先用一部手機每層樓都摔一次，那么我們這里用了最佳策略后，次數就應該小于等于這個值，方程就可以變化為：dp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1),k∈[1,j-1]，
為什么不能用二分，假如說，耐摔指數為249，我們二分的第一次是500，第二次是250，那你要從125開始摔嗎？我們只有3部手機，所以第三次必須從1層開始，顯然不是最佳策略
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[5][1100];
void solve(int phone,int floor)
{
int i,j,k;
for(i=1; i<=phone; i++)
for(j=1; j<=floor; j++)
dp[i][j]=j;
for(i=2; i<=phone; i++)
{
for(j=1; j<=floor; j++)
{
for(k=1; k<j; k++)
dp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1);
}
}
}
int main()
{
solve(3,1000);
printf("%d\n",dp[3][1000]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/272270.html
標籤：其他