有一堆共 M 个鹰蛋，一位教授想研究这些鹰蛋的坚硬度 E。他是通过不断 从一幢 N 层的楼上向下扔鹰蛋来确定 E 的。当鹰蛋从第 E 层楼及以下楼层落下 时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔 碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实 验。教授希望实验是成功的。 例如：若鹰蛋从第 1 层楼落下即摔碎，E=0；若鹰蛋从第N层楼落下仍未碎， E=N。 这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数 M 与楼层数 N。 要求最坏情况下确定E 所需要的最少次数。
dp[i][j]表示用 i 个蛋在 j 层楼上最坏情况下确定答案所需要的最少次数 若蛋在w层碎了，那么答案在w-1那些层里面，（w是二分来的，因为二分是理论上快的），fdp【i-1】,【w-1】+1 若没碎，答案在w到n的那些层里面，dp【i】【j-w】)+1 两个中取较大的值，因为是最坏条件下，所以这两种都可能发生的话选更不好的， 循环ijw O(n^3) 优化： 首先如果蛋很多，多到够二分，那么结果一定是二分的值 2. 如图可以看出best的位置是dp最优选择，所以二分找dp【i-1】【w】 = dp[i][j-w]的w值。。
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> using namespace std; const int maxn = 1100; const int inf = 1e9+7; int dp[2][maxn]; int egg,n; void bi_Se(int f,int i,int j){ int l = 1 , r = j; while(l <= r){ int mid = (l+r)/2; if(dp[f^1][mid-1] > dp[f][j-mid]){ r = mid-1; dp[f][j] = min(dp[f][j],dp[f^1][mid-1]+1); } else if(dp[f^1][mid-1] == dp[f][j-mid]){ dp[f][j] = dp[f^1][mid-1]+1; return ; } else{ l = mid+1; dp[f][j] = min(dp[f][j],dp[f][j-mid]+1); } } } void sov(){ for(int i = 0; i <= n ; i++) dp[1][i] = i; int now = 1,pre =0; for(int i = 2; i <= egg ; i++){ swap(now,pre); dp[now][0] = 0; for(int j = 1; j <= n ; j++){ dp[now][j] = inf; bi_Se(now,i,j); } } printf("%d\n",dp[now][n]); } int main(){ while(~scanf("%d%d",&egg,&n) && (egg || n)){ int tmp = floor(log(n)/log(2)+1); if(egg >= tmp) printf("%d\n",tmp); else sov(); } }