UVA10934&&蓝桥杯测试次数&&鹰蛋问题

UVA10934&&蓝桥杯::测试次数&&鹰蛋问题

​ 以上三种问题都属于一种问题，这里我用鹰蛋问题为例进行分析

参考网址：http://datagenetics.com/blog/july22012/index.html

只有这篇完全诠释了我的所有问题。

我这里只讲述动态规划的解决方案。请耐心看完

$f\left[e\right]\left[k\right]$f[e][k]​代表有 $e$e​ 鸡蛋 $k$k​ 层楼 找出答案的最小测试次数。

• 假设我这次测试时候在第 $1$1​到 $k$k​的第 $i$i​ 层扔鸡蛋。那么分两种情况：

  • 在第 $i$i​层鸡蛋没碎，那么坚韧度在 $[i+1,k]$[i+1,k]​中,即在 $k-i$k−i​ 个连续的层之间，现在我还有 $e-1$e−1​个鸡蛋，那么问题归结到 $f[e-1][k-i]$f[e−1][k−i]​， 即 $f\left[e\right]\left[k\right]=f[e-1]\left]\right[k-i]+1$f[e][k]=f[e−1]][k−i]+1​

  • 在第 $i$i​层鸡蛋没碎，那么坚韧度在 $[1,i-1]$[1,i−1]​之间，即在 $i-1$i−1​个连续的层之间，现在我还有e个鸡蛋，那么问题归结到 $f\left[e\right][i-1]$f[e][i−1]​,即 $f\left[e\right]\left[k\right]=f\left[e\right][i-1]+1$f[e][k]=f[e][i−1]+1​

• 因为这个问题属于运气问题，故是不可控的，因为要求在最坏情况下，故 $f\left[e\right]\left[k\right]=max\left(f\right[e-1\left]\right[i-1],f[e\left]\right[k-i\left]\right)+1$f[e][k]=max(f[e−1][i−1],f[e][k−i])+1

上面就找出了有 $e$e个鸡蛋 $k$k 层楼，在第 $i$i层扔鸡蛋的所需要的最小测试次数,(Remember we need to mimimize the number of drops in the worst case)

虽然运气是不可控的，但是我们选取的 $i$i是可控的，所以我们可以遍历出所有的i，令 $f\left[e\right]\left[k\right]$f[e][k]选取其中最小的

递推式 $f\left[e\right]\left[k\right]=min(max\left(f\right[e-1\left]\right[i-1],f[e\left]\right[k-i\left]\right)+1)),i\in [1,k]$f[e][k]=min( max(f[e−1][i−1],f[e][k−i])+1)),i∈[1,k]

代码记忆化搜索即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int f[1010][1010];
bool iscal[1010][1010];
void init(){
    memset(iscal,false,sizeof(false));
}
int F(int e,int k){
    if(k==0)
        return 0;
    if(e==0)
        return inf;//e=0 k>0 无解
    if(iscal[e][k])
        return f[e][k];
    int minn=inf;
    for(int i=1;i<=k;++i){
            minn=min(minn,max(F(e-1,i-1),F(e,k-i))+1);
    }
    iscal[e][k]=true;
    return f[e][k]=minn;
}
int main(){
    int e,k;
    init();
    while(~scanf("%d %d",&e,&k)){
        cout<<F(e,k)<<endl;
    }
    return 0;
}