入门级动态规划：2018年第九届蓝桥杯省赛B组第四题—测试次数(摔手机)

原题描述：

        x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
        x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
        如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

        为了减少测试次数，从每个厂家抽样3部手机参加测试。
        某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
        请填写这个最多测试次数。

        注意：需要填写的是一个整数，不要填写任何多余内容

        先把答案写在前面 19 ！

        四月省赛时候栽在这道题上了。……昨天蒟蒻博主拿着手机走路楞神，一不小心把手机悠出去了……真*摔手机，拿起买了还没用多久的碎屏手机……莫名想起了这道题！

        当初没有注意到题目中的关键，只提供3部手机供你测试摔手机。直接一个二分法lg1000/lg2<10，交了个10，于是华丽丽的错掉了，二分法虽然可以在最短次数测到最坏可能性，但是致命的是它每次直接从中间高度摔手机，手机很有可能摔坏，如果想要用二分法摔出耐率指数是0的手机，那么足足需要摔坏10部手机！

        还有要说明的是，用二分法摔手机必须要搜索匹配到所有0～1000的值，因为耐率指数可以是0，选择中间值排除另一边或是选取另一边的过程中，对于楼层一来说是不起作用的，因为它需要特别照顾，专门摔它才能知道耐率指数是0还是1。这个陷阱对于1000这个高度没什么，但如果是512层，二分法摔手机就得是10次了( lg513/lg2 )。

        那如果只给了一部手机，怎么测出耐率指数呢？只好从1层开始摔，摔坏了就是(当前层数-1)的耐率指数。假如是两部手机呢？我一开始的想法是对1000进行分块，先用第一部手机摔出目标层数在哪一个小块里，然后再用第二部手机从那个小块最低层一层一层往上摔，直到确认为止。按照这个想法1000层需要分成 a*b*c 三个手机分别负责一个变量，最后就能确认目标层数。

        为了给自己的歪理加个公式增强点可信度，我想到了高中的基本不等式……3√(a*b*c)<=(a+b+c)/3 ，设a*b*c是1000，这么一算a+b+c最小值不就是30吗，a=b=c=10的时候成立。这么看来最难摔到的层数应该就是1000层了，第一部手机摔9次才能确定目标层数在901～1000( 摔101、201…901 )，然后再摔上9次才能确定目标层数在991～1000( 摔911、921…991 )，再摔上9次才能确定是1000( 摔992、993…1000 ）确定出目标层数1000。可能有疑问为什么这里不考虑1了呢，因为我们采用的是自底向上排查，虽然1～10的范围必须要摔上10次才能确定每个值，但是1～10的范围只需要摔101和11就能确定下来( 两次 )，所以我们不考虑它会额外产生次数。因此这种方法摔手机27次能用三部手机摔出目标楼层！

        是不是有点太多了？！！

        ****显然是的，虽说分块分的很合理看上去无懈可击，但是这是建立在分同等长度块的前提下的。找到每个楼层的次数严重不均匀，因为是自底向上的摔，位于前面的楼层可以在短短几次就能确定范围，排在后面的楼层却需要许多次才能确定下范围，这无疑是不公平的，只有位于后面的楼层才会用最大次数摔后确定下来。

        那么为了均衡，把前面的块范围加大，后面块的范围缩小。这样前面的块很快能确定，但是它内部需要很多次才能确定到底是哪一个，而后面的块很多次才能确定但内部很小，因而很快可以确定是哪一个！完美的解决方法……

        如果是20层楼，我们用 2 部手机手机摔。那么最后一个确定的块范围定为1，那么5+5+4+3+2+1 这么划分是最合理的，在每一个块的最后一层扔第一部手机( 这是为了照顾第一层 )，确认下来目标楼层在哪个块之后在块内部用第二部手机扔。第一个块扔一次可以确定，但是内部需要4次；第二个块需要2次确定范围，内部需要4次确定；最后一个块需要摔上5次才能确定，但是内部摔上1次就可以。所以最后的结果应该是6次。这种分法恰好解决了必须要摔1楼的坑！最后一个块必摔一次，前面的块摔长度减一次。

        那当我们有三部手机呢，更深一层的分块，也就是说把全部楼层划分后用两部摔出每个块的内部……继续根据每个块的内部次数分配楼层！！这么来手算就太费劲了，现在看来显然是个动态规划问题了，分解成用 cnt 部手机可以在 ind 楼层最少摔多少次可以确定全部楼层？在一部手机的时候肯定是从1～1000了，一层一层确认。

        自两层开始，每个高度的楼层从底到高依次确定，每个高度都需要从1到当前楼层摔一次手机，判断最坏条件下的次数，之后加一表示此次摔手机，用历史数据的最坏数据和正常一层一层摔手机次数取最小值。可能有疑惑为什么要这么写状态转移方程，因为用指定最大手机数对每一层的最小值可以通过两种可能得到，一个就是上面说的方法中逐层排查比上一层的次数多一，另一个可能就是通过一次摔手机测试后由这次摔手机可以确定的楼层历史数据加一得到( 换句话来说就是有许多较低楼层的历史数据，通过摔一次手机可以将当前楼层分成两部分，摔碎了cnt-1个手机是摔手机楼层k-1；而没碎是cnt手机数不变摔ind-k层，这两个值因为需要照顾所有可能要取最糟糕的，就是最大值，之后加上摔手机的这次+1 )。

        由此可得出状态转移方程： dp[ind][cnt] = Min( 1+dp[ind-1][cnt] , 1+Max( dp[k-1][cnt-1] , dp[ind-k][cnt] )

                                                         2<=k<=ind

#include
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a 
 
        附上代码，输入1000 3即可得到结果 19
 
 
END