rqnoj-107-Ural的鹰蛋实验-dp - c++编程基础

采用了耗时最少的解法，时间复杂度O（sqrt（n））

dp[i][j] ：试验i次，使用j个蛋，最高可测的楼层高度。

dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+1;

对于dp[i][j]:假如试验第一个蛋的时候蛋碎了，那么就得用剩下的j-1个蛋，试验i-1次，能获得的最大楼层高度dp[i1][j-1];

假如试验第一个蛋的时候蛋没有碎，那么就得用剩下的j个蛋，试验i-1次，能获得的最大楼层高度dp[i-1][j];

那么dp[i][j]能获得的楼层高度就为dp[i-1][j-1]+dp[i-1][j]+1;

多以题目就变成了寻找最小的x，使得dp[x][j]>=n;

题目输入的蛋的个数n和楼层高度k。

当n>floor((log(k)/log(2))+1);就可以使用二分法测量;

#include  
#include  
#include  
#include  
#include  
using namespace std;  
int dp[101];  
void dos(int n,int k)  
{  
    int i,j;  
    if(dp[n]>




=k)cout<<1<=2;j--)  
        {  
            dp[j]=dp[j]+dp[j-1]+1;  
            if(dp[j]>=k)  
            {  
                cout<=k)  
        {  
            cout<<1<tmp)  
        {  
            cout<