[动态规划优化] 鸡蛋的硬度 状态重定义

题目描述

有一个教授有一批一模一样的鹰蛋。有一天他来到了一栋楼的脚下，他突然想知道自己的鹰蛋从这栋楼的多少层扔下时恰好不碎。
一颗鹰蛋如果从i层摔下没有碎，那么从小于j层摔下也不会碎，如果从j层摔下碎了，从大于j层摔下也会摔碎。如果恰好存在一层n，从n层摔下鹰蛋未碎，而从n+1层摔下碎了，那么这批鹰蛋恰好从n层摔下未碎。如果从第一层摔下碎了，那么称恰好从0层摔下未碎；另一方面，如果从最高层（N层）摔下未碎，那么称恰好从N层摔下未碎
这个教授想知道从第多少层恰好摔下不碎，但是这个教授想使用最少的试验次数来得到这个值。
现已知鹰蛋的个数M和楼层高度N，试问在最坏情况下，这个教授最少需要试验多少次来得到他想要的结果？
比如：M为1，N为3。那么这个教授为了得到结果，就必须从一层一层测试，在最坏情况下，最少需要3次试验。但是如果M=2,N=3，那么他就可以第一次从二层扔下，不管碎了还是没碎，他都只需再扔一次即可得到结果，即需要做2次试验即可。

关于输入

有多组输入，每一组输入单独一行。
分别为两个如题所述的正整数N（大于0小于400001），M （大于0小于N+1）中间用空格隔开。
如果得到的N和M都为0，表示输入结束。

关于输出

每组输出单独一行，输出需要试验的次数K。

例子输入

100 1
100 2
0 0

例子输出

100
14

提示信息

动态规划，由于输入量比较大，最好尽量优化算法。

解题分析

首先介绍一种初级的方法，这种方法可以用来解决小数据的情况。我们定义一个dp数组，其中dp[i][j]表示用i个鸡蛋去测j层楼在最坏的情况下所需要测试的最少次数。

接下来，我们需要考虑如何去更新这个dp数组。首先，我们可以知道的是，如果我们手头只有一个鸡蛋，那么，在运气最差的情况下，我们不得不从第一层开始测，所以这个时候的最少次数就是楼层的层数。

如果我们只有一层楼，那么根据题意，无论我们这一下鸡蛋碎没碎，我们都可以定义这个鸡蛋的硬度了，所以这个时候我们的最少的次数就是1。

在其他情况，假定我们有m个鸡蛋需要测试n层楼，我们怎样可以得到运气最差的情况下测试所用的最少的次数呢？一个想法就是去枚举期我们所扔第一个鸡蛋的层数。我们可以假定我们第一个鸡蛋一开始从k层去扔，那么，如果碎了，我们的问题就变成是用m-1个鸡蛋测k-1层楼；如果没碎，我们的问题就变成是用m个鸡蛋去测n-k层楼。

代码实现1

#include <iostream>
using namespace std;
 
int dp[200][200]={0};
 
int f(int n,int m){
    if(dp[n][m]) return dp[n][m];
    if(m==1) return n;
    if(n==1) return 1;
    int res=1e9;
    for(int k=1;k<=n;k++){
        res=min(res,max(f(k-1,m-1)+1,f(n-k,m)+1));
    }
    return dp[n][m]=res;
}
 
int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0 && m==0) return 0;
        cout<<f(n,m)<<endl;
    }
    return 0;
}

当然直接用for循环打表也可以:

#include <iostream>
using namespace std;
 
int dp[100000][100]={0};
 
int main(){
    int n,m;
    while(cin>>n>>m){
    if(n==0 && m==0) return 0;
    for(int i=1;i<=n;i++){
        dp[i][1]=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++){
            dp[i][j]=i;
            for(int k=1;k<=i;k++){
                dp[i][j]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);
            }
        }
    cout<<dp[n][m]<<endl;
    }
    return 0;
}

解题分析2

当然，如果仅仅如此的话，还不能完美的解决本题，因为我们可以发现，N的值很大，而我们现在的这算法的时间复杂度是n^2*m，当N大于10000时，我们就会超时了。

如果去优化呢？这里需要采用状态重定义的技巧。我们发现，dp[n][m]表示m个鸡蛋测n层楼，当鸡蛋的数目一定时，我们增加楼层的数量，可以发现需要尝试的次数也会增加，也就是说，这两个量是成正比的关系，而从直观上理解，尝试的次数作为一个取min的量，其值肯定要比楼层数要小的多，所以我们可以重新定义一下dp数组的状态。

我们交换尝试的次数和楼层数的位置，dp[i][j]表示i个鸡蛋尝试j次可以到达的最大楼层数。这样，当我们发现dp[i][k-1]小于n时，说明k-1次不能测出鸡蛋的硬度，且我们发现dp[i][k]>=n，那么我们要求的次数就是k次。（相当于对我们之前那个过程的逆向处理）。

于是dp[i][j]=dp[i-1][j-1]（有可能鸡蛋碎了，那就测下面的楼层）+dp[i][j-1]（有可能鸡蛋没碎，那就测上面的楼层）+1（当前的这个楼层）。

 代码实现

#include <iostream>
#define Max_trial 100
#define MaxM 400005
using namespace std;
 
int dp[MaxM][Max_trial]={0};
 
int main(){
    int n,m;
    for(int i=0;i<Max_trial;i++){
        dp[1][i]=i;
    }
    for(int i=2;i<MaxM;i++)
        for(int j=1;j<Max_trial;j++){
            dp[i][j]=1+dp[i][j-1]+dp[i-1][j-1];
        }
    while(cin>>n>>m){
        if(n==0 && m==0) return 0;
        if(m==1) {
            cout<<n<<endl;
            continue;
        }
     for(int i=0;i<Max_trial;i++){
        if(dp[m][i]>=n){
            cout<<i<<endl;
            break;
        }
     }
    }
    return 0;
}