作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4098409.html
题目链接：poj 3783 Balls 动态规划 100层楼投鸡蛋问题
使用动态规划算法，使用$dp[i][j]$表示对于i层楼并拥有$j$个鸡蛋时能够判断鸡蛋质量需要的最少次数。
假如我们在第$k$层扔下一个鸡蛋，则有两种情况，如果鸡蛋没有损坏则问题相当于我们对于$i-k$层楼拥有$j$个鸡蛋所需的最少的次数。
如果鸡蛋损坏了，则问题相当于对于k层楼拥有$j-1$个鸡蛋的最小次数。从而可以得到动态规划公式：
\begin{equation}
dp[i][j] = Min(Max(dp[k][j-1],dp[i-k][j])),k\in[1,i)
\end{equation}
数学方法推倒：
如果我们有$2$个鸡蛋，$k$次投掷机会，那么第一次在$k$层投掷，如果坏掉，则从第一层往上投。
否则剩下$k-1$次机会，所以要在$k+(k-1)$层投掷，如此往复，两个腕带可以投掷的最高楼层为：
\begin{equation}
\sum_{i=1}^k i = \frac{k(k+1)}{2}
\end{equation}
对于三个鸡蛋k次机会，根据上面的结论，两个鸡蛋$k-1$次可以测试$k(k-1)/2$层楼，所以第一次在$k(k-1)/2+1$层投，如果坏掉，则从第一层往上投。
否则剩下k-1次机会和两个鸡蛋，则在此基础上增加$(k-1)(k-2)/2+1$层投掷，如此往复。三个鸡蛋可以投掷的最高层为：
\begin{equation}
\sum_{i=1}^k \frac{i(i-1)}{2}+1 = \frac{k^3+5k}{6}
\end{equation}
代码如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <limits.h>
#define MAX_F 1001
#define MAX_E 100
using namespace std;
int dp[MAX_F][MAX_E];
int solve(int floor, int egg)
{
memset(dp, , sizeof(dp));
for( int i = ; i <= floor ; i++ )
{
dp[i][] = i-;
}
for( int i = ; i <= egg ; i++ )
{
dp[][i] = ;
}
for( int i = ; i <= floor ; i++ )
{
for( int j = ; j <= egg ; j++ )
{
int tmp = INT_MAX;
for( int k = ; k < i ; k++ )
{
tmp = min(tmp, max(dp[k][j-] , dp[i-k][j]));
}
dp[i][j] = tmp+;
}
}
return dp[floor][egg];
}
int main(int argc, char *argv[])
{
int t;
scanf("%d", &t);
while( t-- )
{
int n, egg, floor;
scanf("%d%d%d", &n, &egg, &floor);
printf("%d %d\n",n, solve(floor, egg));
}
}