本文共 1097 字，大约阅读时间需要 3 分钟。

题意：

给出k个水球，n层楼，现在想测试出水球最低会在那层楼扔下爆炸，问最少需要测试多少次， 注意要求的情况是每层楼都可能爆炸。

解题思路：

一眼看上去会觉得是二分，如果求数够的话，确实能够在log2(n)的次数之内求出测试出来，但是这个问题我们要考虑的是每个位置都有可能爆炸，所以不仅球不够，目标位置没有确定也导致我们不可能考虑二分。

想一想如果去搜索的话，我们肯定会搜索还剩下i个球，已经测试了j次的状态。我们搜索i,j状态下最高能够测试到在什么位置爆炸的高度h,如果i-1, j-1能够测试到h，那么i, j就最少能测试到h+1，这是在h+1这个位置爆炸了的情况，如果没有爆炸的话，对于i, j这个状态就转换为了i, j-1，由于在h+1测试过了，加上还剩下的i, j-1状态能够测试的h2，那么对于h1+1+h2高度内的所有不同位置是最低爆炸点的情况我们都爆炸可以求出来了（这里非常重要，想一想）.

当然想搜索是为了确定dp的状态的，通过搜索起码可以想到状态应该怎么表示。而转移其实就是刚刚上面讲的了。

注意判k=0， n!=0的情况。

代码:

#include 
   
    #define LL long longusing namespace std;LL dp[105][66];int main(){    LL n;    int k, i, j;    LL mi=10;    for(i=1; i<=100; i++)    {        for(j=1; j<=63; j++)        {            dp[i][j]=dp[i-1][j-1]+1LL+dp[i][j-1];        }    }    while(~scanf("%d%lld", &k, &n))    {        if(k==0)break;        if(n==0){printf("0\n");continue;}        int ans=64;        for(i=1; i<=k; i++)        {            for(j=1; j<=63; j++)            {                if(dp[i][j]>=n)ans=min(ans, j);            }        }        if(ans==64)printf("More than 63 trials needed.\n");        else printf("%d\n", ans);    }}
   

转载地址：http://eoywb.baihongyu.com/