高楼抛玻璃球（鸡蛋）问题

经典的抛鸡蛋问题如下：

幢 200 层的大楼，给你两个鸡蛋，如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从第 n-1 层扔鸡蛋，都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次，且鸡蛋在0层不会碎。设计一种策略能保证可以测出鸡蛋恰好会碎的楼层，且如果该策略是最坏的情况所扔次数最少。

分析：

---

　　第一次抛鸡蛋肯定是从某一楼开始抛的，这里我们假设我们第一次从第n层开始抛。那么，这时有两种结果

　　1，鸡蛋碎了

　　　　由于只有2个鸡蛋，为了准确测出鸡蛋恰好碎的楼层，我们不得已从第一层开始测试，最坏的情况是一直测试到n-1层，那么整个过程我们测试了n次。

　　2，鸡蛋没碎

　　　　此时，我们需测试n+1层到200层。这个时候应该采取什么样的策略呢？我们已经知道在第n层鸡蛋碎的情况下，最多要测试n次。那么，我们考虑的是，在鸡蛋没碎的情况下，我们测试n+1到200层，最好也不要超过n次。能做到这样吗？能。我们采取这样的做法：

　　　　在第n层往上数n-1层，测试n+n-1层。若碎了，那么，恰好碎的楼层在n~n+n-1之间，那么其最多要测试1+1+n-2次，即恰好碎的楼层在n+n-2层，我们从n+1到n+n-2层，要测试n-2次，而前面还有测试n，测试n+n-1层，共1+1+n-2=n次。若没碎，我们在n+n-1的基础上，往上数n-2层，测试n+n-1+n-2层，若碎了，那么恰好碎的楼层在n+n-1层到n+n-1+n-2之间，那么我们最多要测试1+1+1+n-3层，即恰好碎的楼层在n+n-1+n-3层，我们从n+n-1+1到n+n-1+n-3要测试n-3层，而前面还要测是n，n+n-1，n+n-1+n-2层，共1+1+1+n-3=n次。

　　　　若在n+n-1+n-2层也没碎，那么我们继续上面的策略，其最坏次数是不会超过n次的。那么，对于200层，我们就有如下表达式n+n-1+n-2+....+1=200，这里的n既是最坏的测试次数也是第一次测试的楼层数。

　　　　所以，在楼层数为M的情况下，有n(n+1)/2=M，解方程可得最坏测试次数。

进阶：

---

　　前面的讨论中，我们只要求有两个球（蛋）。现在，我们不限制这个条件，在N个球，M层的情况下，求最坏测试次数。这个时候，前面的分析不在适用。我们作如下考虑，

　　假设i个球，j层所需测试次数为dp[i][j]。

　　我们第一次从第k层开始测试，

　　1，在第k层碎了，我们还剩 i-1 个球，k-1层需测试，需要dp[i-1][k-1]次，共dp[i-1][k-1]+1次

　　2，在第k层没碎，我们还剩 i 个球 ，j-k层需测试，需要dp[i][j-k]次，共dp[i][j-k]+1次

　　所以，第一次从第k层开始测试的最坏次数 dp[i][k] = max(dp[i-1][k-1]+1, dp[i][j-k]+1)。我们遍历0~j层，取最小次数，即可得i个球，j层所需测试次数dp[i][j]。

　　dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], dp[i][j-k]))

　　显然，这里用的就是动态规划。

　　废话少说，show me code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define MOD        1000000007ll
#define PI         acos(-1.0)
const double EPS = 1e-6;
//const double PI  = acos(-1.0);
const int INF = 0x3f3f3f3f;
//const LL  MOD = 1e9+7;

template <class T> inline T bigMod(T p, T e, T M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret % M;    // Attention: bigMod(p, 0, 1), so ret has to module M.
}
template <class T> inline T modInverse(T a, T M){return bigMod(a, M-2, M);}
template <class T> inline T gcd(T a, T b){return b ? gcd(b, a%b) : a;}

int main() {
    const int maxN = 51;
    const int maxM = 1001;
    int dp[maxN][maxM];
    int T, t, n, m;
    memset(dp, INF, sizeof(dp));
    for (int i = 0; i < maxM; ++i) {  // only one ball
        dp[1][i] = i;
    }
    for (int i = 0; i < maxN; ++i) {  // the floor is 0 or 1
        dp[i][1] = 1, dp[i][0] = 0;
    }

    for (int i = 2; i < maxN; ++i) {
        for (int j = 2; j < maxM; ++j) {
            for (int k = 0; k < j; ++k)
            dp[i][j] = min(dp[i][j], max(dp[i-1][k-1]+1, dp[i][j-k]+1));
        }
    }

    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &t, &n, &m);
        printf("%d %d
",t, dp[n][m]);
    }

    return 0;
}

　　其实，这道题来自POJ 3783 Balls。由于poj不支持#include <bits/stdc++.h>, 所以，头文件改为如下即可：

#include <iostream>
#include <cstring>    //   引入memset

　　哎，写这么一会儿，脖子就酸了。