题目：测试次数
星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机！
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。####特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
为了减少测试次数，从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
请填写这个最多测试次数。
注意：需要填写的是一个整数，不要填写任何多余内容。
看到题目的第一眼👀，我的直观感受就是二分法哇，太简单了，捡到了捡到了。
后来，考完很久以后，我又重新刷题，感觉不对，应该不是这么简单的。应该是DP动态规划！
题解：
1、理解题意：
已知n是耐摔指数，有3部手机，求解最坏情况下至少摔K次。
在此题，n可能是区间[0,1000]上的任意一个数字，那么我们保证在K次里，不论n = 0，1，... ，1000 中的哪个数字，我们都能准确确定n的值。
2、抽象成模型：
抽象成一根数轴，n在区间[0，1000]
我设dp[ind][cnt]为 ind为区间长度，cnt部手机，数组dp记录确定n需要的局部最少次数。
如果只有 1 部手机，那就只能从小到大，一次一次实验。直测试出n。
如果有 2 部手机，我们开始分块，
分成1：999，2:998，3:997，...... 诸如此类 所以我也不知道哪种分块最优啊，当然是暴力遍历一遍啦！
这时候状态就可以转化成：到底碎不碎了？
如果在K层碎了，问题就等价成：搜索区间 [0,k-1]的次数 + 1；
如果在K层没有碎，问题就等价成：搜索区间[k+1，1000]的次数 + 1；
思考一下，确定n[k,1000] 所需要的次数 是不是 等价于 确定n
[0,1000 - k] 所需要的次数！因为区间长度一致哇！
如果有cnt部手机，ind层时，
dp[ind][cnt] = Min(dp[ind-1][cnt]+1 , 1+Max( dp[k - 1][cnt - 1] , dp[ ind-k ][ cnt ] ) )
解释一下 用Max函数和Min函数：
我们本意是写一个算法，实现对n是任何可能值的求解。
假设层数是6，2部手机，看图解：
结论：题目实际是求全局最优解——常用方法DP！
DP：全局最优——>局部最优——>求动态转移方程
就是用动态规划的思想，去走遍所有所可能的情况，通过条件限制，求最小次数啦。
Max：最坏情况的判断，n=2是最好情况，可是如果这些手机耐摔指数
n=0，1，2，3，4，5，6呢！
Min：最少次数的选择，情况虽然不妙！但是我们可以尽量少花力气去摔手机哇！
选出确定dp[ ind ][ cnt ]需要的最小次数。
状态方程就这么总结出来啦！！！
dp[ind][cnt] = Min( dp[ind-1][cnt]+1 , 1+Max( dp[k - 1][cnt - 1] , dp[ ind-k ][ cnt ] ) )
3、代码实现：
#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;
}
第一次写题解，写得不好的地方请大家指出。帮我进步！（其实放图是因为我不会换行）
网友评论