面试很热门的抛鸡蛋问题

分析
Q: 只给你二个鸡蛋，你能上100层楼，你想知道鸡蛋的硬度。鸡蛋可能很硬或很脆弱，如果鸡蛋从第m层掉下而没破裂，而从第m+1层掉下就破裂了，那么这个鸡蛋的硬度就是m。你需要找出这个m和在最坏情况下最少试验次数。(经典鸡蛋问题)
A: 计算机学生可能会首先用第一个鸡蛋做二分搜索(O(logN))再用第二个递增做线性搜索（O(N)），最后必将用线性搜索结束因为用第二个鸡蛋时你无法确定最高一层。因此，问题变为如何使用第一个鸡蛋来减少线性搜索。
于是如果第一个蛋破裂在最高点我们要扔x-1次并且我们必须从x层高扔第一个蛋。现在如果第一个蛋的第一次扔没有破裂，如果第一个蛋在第二次扔破了我们要扔x-2次第二个蛋。假如16是答案，我需要扔16次才能找到答案。来验证一下是否可以从16层开始扔，首先从16层扔如果它破裂了，我们尝试所有其下的楼层从1到15；如果没破我们还能扔15次，于是我们将从32层(16+15+1)再扔。原因是如果它在32层破裂我们能尝试其下所有楼层从17到31最坏扔第二个蛋14次（总共能扔16次了）。如果32层并没破，我们还剩下能扔13次，依此类推得：
1 + 15 16 如果它在16层破裂，从1到15层最坏扔15次第二个蛋
1 + 14 31 如果它在31层破裂，从17到30层最坏扔14次第二个蛋
1 + 13 45.....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 在最后我们能轻易地做到因为我们有足够多扔的次数来完成任务
从上表我们能看到最佳的一个在最后一步将需要0次线性搜索。
能把上述规律写为: (1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
令1+p=q上述式子变为q(q+1)/2>=100,对100解答得到q=14。
扔第一个蛋从层14，27，39，50，60，69，77，84，90，95，99，100直到它破裂，再开始扔第二个蛋。最坏情况只需14次。

代码
设计一个状态f[i][j]，表示有i层楼j个鸡蛋，最坏情况下要扔鸡蛋的次数。
由于一个鸡蛋扔下去就只有破和不破两种可能，所以状态转移就是f[i][j] = min(1+max(f[k-1][j-1], f[i-k][j]))，(1 <= k <= i)。如果要构造出一个可行解的话，稍微修改一下代码，记录下路径就应该可以了吧。

#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

const int MAXN = 1001; // change it to the number you want
const int MAXM = 1001;

int n; // the number of floors
int m; // the number of eags
int f[MAXN][MAXM]; // the result

void init()
{
   memset(f, 0, sizeof(f));
   for (int j=1; j<MAXM; j++)
   {
       for (int i=1; i<MAXN; i++)
       {
           if (j == 1)
               f[i][j] = i;
           else{
               for (int k=1; k<=i; k++)
               {
                   int tmp = 1+max(f[k-1][j-1], f[i-k][j]);
                   if (f[i][j]==0 || f[i][j]>tmp)
                       f[i][j] = tmp;
               }
           }
       }
   }
}

int main()
{
   init();
   printf("Hey cin n, m\n");
   while (scanf("%d%d", &n, &m) != EOF)
       printf("%d\n", f[n][m]);
   return 0;
}