【蓝桥杯】 第九届国赛 第四题 测试次数（动态规划）

第九届国赛 第四题 测试次数问题描述x星球的居民脾气不太好但好在他们生气的时候唯一的异常举动是摔手机各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试并且评定出一个耐摔指数来之后才允许上市流通x星球有很多高耸入云的高塔刚好可以用来做耐摔测试。塔的每一层高度都是一样的与地球上稍有不同的是他们的第一层不是地面而是相当于我们的2楼如果手机从第7层扔下去没摔坏但第8层摔坏了则手机耐摔指数7特别地如果手机从第1层扔下去就坏了则耐摔指数0如果到了塔的最高层第n层扔没摔坏则耐摔指数n为了减少测试次数从每个厂家抽样3部手机参加测试。某次测试的塔高为1000层如果我们总是采用最佳策略在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢请填写这个最多测试次数。注意需要填写的是一个整数不要填写任何多余内容。---分割线---思路一编程角度首先需要注意本题中的手机是没有后效性的即没有扔坏的话可以当作新的继续扔然后这道题明显存在着某种递归关系仔细看题目中很关键的一句话“总是采用最佳策略在最坏的运气下最多需要测试多少次”好了看到这句话基本可以确定的是这是一个dp动态规划那么我们需要先确定一下dp的元素楼层数、手机数一. 根据变量制表图中白色空格中内容为仅有i层楼时利用j个手机在最佳策略但运气最坏下的摔手机次数表格中红色部分即为题目要求解数量过大不可能人脑推算只能编程为此我们先人工填表找规律对应数据结构就是一个二维数组int dp[1001][4] 从1开始二.完善表格手机数量为1时在手机仅有一个时为了保证能够测试出耐摔指数就只能一层一层的摔所以有几层就要摔几次并且测试方法只能是从第一层楼逐渐往上摔直到手机摔碎或者到顶。即第一行的表格只能填写为对应代码如下:for(int i 1 ; i1000 ; i) dp[i][1] i;手机数量为2时1层楼时情况和手机数为1时一致均为1。2层楼时由于总是遇到最坏的运气何谓最坏的运气这么给你解释吧现在两层楼两个手机让你测试耐摔指数。你有两个方案1.先从1楼开始测试2.先从2楼开始测试注意这里是因为总楼层低(只有2层)你才可以从2楼先扔要是楼层高了你从大于2的楼层开始扔是不能保证能测试出手机的耐摔指数的换言之这里(楼层数2)你先从2楼扔是一种特殊情形现在假设从1楼开始测试由于你运气不好那么意思就是你还要再测试一次也就是说在1楼扔下去没有摔坏你还需要再去2楼测试一次。至于最后的结果如何我们不关心总之你需要测试两次同样地假设现在你从2楼开始测试那么由于运气不好同样地你也要再测试一次也就是说在2楼扔下去摔坏了那么你需要换另一个手机再去1楼测试一次。同样地这之后的结果如何我们不关心反正总的你要测试两次。总结看来这个最坏的运气就是指你总是在往着测试次数更多的方向发展。于是通过以上分析可以先得到以下表这时候来看当存在3楼时的情况首先要知道前面2部手机2层楼时是一定可以保证你能得到手机的耐摔指数的现在是2部手机3层楼那么我们是可以在前面的结论的基础上进行测试的也就是说假设前面先测试第1层楼运气最坏嘛那就要继续测试也就是说在1楼没坏那接着测试第2层楼同样地运气最坏嘛那就不能坏继续摔于是接着测试第3层楼。共3次。显然上面的这个分析给出了一个关系当多一层楼时dp[i][j]总是存在一个最差关系即dp[i][j]dp[i-1][j]1反正前面楼的测试结果为dp[i-1][j]嘛那么现在多一层楼我最差的情况也就仅仅比这个情况多测试一次因为最坏运气的原因必定让你再多上一层楼即dp[i][j]dp[i-1][j]1也就是说3楼2手机的空格位置处可以填的最大值为3那么最小值呢实际上我们知道当多一层楼时也许会有一个更优的方案有这种可能但也可能没有比如现在接着这个情况分析2部手机3层楼由于我有两部手机那我可以冒险一点不用一层一层的扔。之前必须一层一层的扔是因为当时只有一部手机如果你不一层一层扔那么当某次扔下去坏了而你又是从中间某个位置扔的那么你就不知道手机的耐摔指数到底是多少。比如50层楼你从25层扔下去摔坏了那你也不知道这个手机的耐摔指数是多少了。因此必须一层一层扔。可现在你有两部手机那么情况就不一样了你是可以从中间某个位置去扔以降低测试次数。现在的问题便是从中间哪个位置才合适呢你想为了让你发挥出具有两个手机的优势你一定会存在的保障是当第一部手机摔坏了此时第二部手机能够从刚才摔坏的位置继续执行任务。不同的是这一次你必须保证能测试出其耐摔指数。那么这时你仅剩下一部手机不是和之前只有一部手机时的情况如出一辙么?也就是只能一层一层的测试了。那也就是说当你有两部手机时每次测试时你只需保证与已经测试了的楼层有2层楼的间隔以保证当这一次摔坏了只剩下中间一层时你仍然能完成测试任务这时你只需要测试中间这一楼就一定可测出。这也就是我们所采用的最优策略了。回到3层楼这里2部手机那么我们就直接测试第2层楼如果坏了那么我们就测试1楼共测试两次不关心最后测试坏还是没坏反正能得出总的测试结果如果没坏那么我们就测试3楼共测试两次不关心最后测试坏还是没坏反正能得出总的测试结果于是可以得到以下表格三.总结规律①每个空的最大值即保证每个空至少能有一个测试次数不至于空着没答案由于我们可以确定每个空的最大值为其前一楼层次数1例如求2个手机3层楼时的测试次数时在已测试出了两层楼的测试次数的前提下在3楼再摔一次一定可以得到3楼的次数 即 每个dp[i][j]的最大值总是满足dp[i][j] dp[i-1][j]1②每个空的最优值也许会和最大值相等当采用最优策略时在中间某层(设为k)扔会有两种情况1.损坏说明楼层过高接下来应尝试当前层下面的k-1层但手机数-1: dp[i][j]dp[k-1][j-1]12.未损坏说明楼层不够高接下来应尝试当前层上面共n-k层假设总楼层数为n此时手机数没变dp[i][j]dp[n-k][j]1这时候到底选那种情况呢题目说了总是遇到最坏的运气而前面我也说了最坏的运气在我们的程序中体现为接下来测试的次数会更多。即我们的代码应该是dp[i][j] max(损坏未损坏 max(dp[k-1][j-1]1,dp[n-k][i]1)这也就是我们的递推式子了下面给出本题完整代码#includeiostreamusingnamespacestd;intmain(){intdp[1010][5]{0};//dp[i][j]:在仅有i层楼时使用j个手机需要摔的最大次数for(inti1;i1000;i)//只有一个手机时几层楼就要摔几次确保能测出耐摔指数dp[i][1]i;for(inti2;i3;i)for(intj1;j1000;j){dp[j][i]dp[j-1][i]1;//赋最大初值(楼层每增加一层其需要摔的次数一定会小于等于其楼层数减一的次数1for(intk2;kj;k)//最优策略在中间楼层逐个寻找以找到测试次数最多的那个dp[j][i]min(dp[j][i],max(dp[k-1][i-1],dp[j-k][i])1);//外部的min表示着采用最优策略而内部的max则是指每一个最优策略都是在受到最坏运气的影响下得到}coutdp[1000][3]endl;return0;}思路二纯数学角度参考自博客:https://blog.csdn.net/nka_kun/article/details/79789511要知道这是一道填空题无论什么手段只要能得到答案就行这种具有很浓烈的数学味道的题况且还是填空题大多数情况下我们的第一反应都应该是想能不能以纯数学的方法来求解。在分析这道题之前我们先引入一个100层楼扔两个鸡蛋的问题两个软硬程度一样但未知的鸡蛋它们有可能都在一楼就摔碎也可能从一百层楼摔下来没事有座100层的建筑要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋最少需要几次测试才能得到摔碎鸡蛋的楼层方案如何对这个问题原始问题——【两个鸡蛋100层楼最少需要几次测试才能得到摔碎鸡蛋的楼层】直接考虑不容易考虑但是如果将这个问题进行一种等价的转换这个问题将会变得非常容易解答。个人认为这个转换是解决这个问题的核心这个转换是转换问题——【两个鸡蛋进行k次测试最多可以测试几层楼】如果大家能想到将“原始问题”变为“转换问题”其实就已经解决了一半现在我们以“转换问题”为模板进行考虑有两个鸡蛋第一个鸡蛋如果破碎第二个鸡蛋就必须只能一层一层的测试了并且我们要求进行k次测试就一定能将摔碎鸡蛋的楼层找到考虑第一次测试。第一次测试的时候第一个鸡蛋放置的楼层不能太高了否则如果第一个鸡蛋破碎第二个鸡蛋可能不能在k次测试后得到结果。但是也不能放置的矮了因为如果放置的矮了第一个鸡蛋破碎了还好说如果没破我们浪费了一次测试机会也不能说是完全浪费了不过至少是让效用没有最大化。所以第一次测试的时候必须让第一个鸡蛋的放置位置不高不矮。不高不矮是多高高到如果第一个鸡蛋破碎后第二个鸡蛋刚好能在剩下的k-1次中将这剩余的楼层数量测试出。由此可知第一次测试所在的楼层高度就应该刚好为k。这样一来如果第一次测试第一枚鸡蛋破碎则剩下k-1层楼一层一层的试k-1次内一定能完成目标因为刚好剩下k-1次机会嘛这样就使得每一次的机会都最大化了其效用。如果第一次测试第一枚鸡蛋没有破碎则我们现在只有k-1次测试机会了但却测试出了k楼及其以下都是安全的。我们消耗了一次测试机会但是一次就测试了k层楼。然后只有k-1次机会了第二次测试我们可以在k层的基础上再增加k-1层了注意这个时候由于我们只有k-1次机会所以这次只能再增加k-1层以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。于是重复上述过程直到最后一次机会那么我们总共测试的楼层数就为然后再回到“原始问题”100层楼如果需要k次测试才能测试完成则必须有:则可以得到k≥14也就是至少需要14次测试才能得到结果而且这个过程也将测试方案一并得出来就是第一次在14楼测试如果第一枚蛋碎则剩余13次机会13层未知楼层恰好。如果没碎则第二次在141327楼测试如此循环。如果不是100层而是N层需要的测试次数为k则有然后这个问题此时就可以扩展了如果我们有三个鸡蛋有k次机会我们最大可以测试多少层楼思路同前面一样第一次测试不能太高也能太矮必须恰到好处也就是第一枚鸡蛋如果破碎剩余k-1次机会能将剩余楼层给测试完。由上面结论两个鸡蛋k-1次机会最多可以测试k(k-1)/2层楼所以第一次在k(k-1)/21层楼第一次如果第一枚鸡蛋不碎第二次在此基础上增加(k-1)(k-2)/21层楼于是三个鸡蛋k次机会总共测试楼层数为:至于四个鸡蛋五个鸡蛋以至于M个鸡蛋可以以此类推方法同上。再回到本题中来3个鸡蛋1000层楼那么我们直接带上面已经推出来的公式即解之即可可以验证两种思路下得到的结果均一致为19