大楼扔鸡蛋问题 dp poj 3783

傷城~ 2022-08-18 12:25 2阅读 0赞

题意分析： 经典题，小白书上的一道例题，4+2出了这道原题，我愣是以为是数学题，最后也没做出来。题意是这样的，给你N个鸡蛋（硬度一样），让你测鸡蛋的硬度，测量的方法就是从某栋M层的楼的某一层X上把鸡蛋扔下来，如果鸡蛋碎了，代表他的强度小于X；如果没碎，则强度大于等于X。我们要做的就是不断的从楼上把鸡蛋扔下来，直到找到某一层楼X，从这一层楼扔下来鸡蛋不碎掉，从X+1层扔下来鸡蛋碎掉，那么鸡蛋的强度就是X。如果在M层扔下来鸡蛋也不碎掉，那么鸡蛋的强度为M。问题是，用N个鸡蛋最多需要几步可以把硬度测出来（鸡蛋碎掉就不能用了，而且必须测出来！）。

解题思路： 一开始看懂题意之后，我马上就想到了二分法，但是仔细一想并不对，如果鸡蛋的数量足够的话，二分法绝对是最快的，但是如果鸡蛋不够，就不太一样了。如果第一次扔就碎了一个鸡蛋，那么剩下的鸡蛋就只能从下往上测试，这样2个鸡蛋、100层楼的情况最多可能需要51步，然而测试样例告诉我们，只要14步，当时想了足足有半个钟才想到他可以用\{ 14，13，12 …… \}这样的步长进行测试，这样最多的测试数都是14次，这样的原则确确实实可以解决2个鸡蛋的问题，但是3个鸡蛋就跪了，于是有了动态规划算法。   
动态规划算法：   
状态：   
dp\[i\]\[j\]表示N=i，M=j时，最多需要多少次测试。   
状态转移方程：   
如果我们一开始是在k层进行测试的，那么如果鸡蛋破碎了，我们的查找范围就变成k层一下的k-1层，当然此时鸡蛋数减少了，所以最终的步数应该为dp\[i-1\]\[k-1\]+1；另外一种情况是鸡蛋没有碎的情况，我们要找的范围变成了k层以上的，所以最终需要dp\[i\]\[j-k\]+1步。我们的目标就是要找到一个k，使得最坏情况下测试数最少，所以我们需要枚举k。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <string>
    using namespace std;
    
    #define INF 0x3f3f3f3f
    int dp[55][1005];
    int n,m,c;
    
    void cal()
    {
        memset(dp,INF,sizeof(dp));
    
        for(int i = 1 ; i < 55 ; i++)
        {
            dp[i][1]=1;dp[i][0]=0;
        }
        for(int i = 1 ; i < 1005 ; i++)
        {
            dp[1][i]=i ;
        }
    
        for(int i = 2 ; i < 55 ; i++)
        {
            for(int j = 2 ; j < 1005 ; j++)
            {
                for(int k = 1 ; k < j ; k++)
                {
                    dp[i][j] = min(dp[i][j],max(dp[i][j-k]+1,dp[i-1][k-1]+1));
                }
            }
        }
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        cal();
        while(t--)
        {
            scanf("%d%d%d",&c,&n,&m);
            printf("%d %d\n",c,dp[n][m]);
        }
        return 0;
    }

PS:这个题目很典型也很经典，各种版本的都有，但基本的意思是一样的。

但是这个题目变形之后的一种是，楼层非常高达到2000000007，另外假如32次还不能确定最终的答案的话就直接输出不可能。

这样我就有点不确定怎么写了，应该要做个初始化吗，还是怎么样，直接dp肯定是不行的。求大神帮忙。