题目链接：https://vjudge.net/problem/27377/origin
题意：
有一栋n层高的楼，并给你k个水球。在一定高度及以上将水球扔下，水球会摔破；在这个高度以下扔，水球不会摔破，并且可以捡起来再用。现在你要通过不断地试扔水球，找出在这栋楼上的第几层扔水球，恰好能让水球摔破。问你在最坏情况下，最少扔几次可以保证找出这个层数（若大于63次则输出‘More than 63 trials needed.’）。
题解：
这个问题可以转化成：
花费i个球，j次扔水球，最多能确定几层（也就是确切地知道在这几层中的任意一层扔水球会不会摔破）。
也就是dp[i][j] = max floors
最后统计一下在 i<=k , j<=63 的条件下是否存在dp[i][j] >= n，如果有，则输出符合条件的最小的 j ；如果没有则输出‘More than 63 trials needed.’。
假设你在第x层扔了一次水球，总共分为两种情况：
（1）水球破了，那么要找的这个高度一定在 x 及以下。扔这一次花费了1个水球和1个扔的次数，在这之后还可以往下确定dp[i-1][j-1]层。
dp[i][j] += dp[i-1][j-1]
（2）水球没破，那么要找的这个高度一定在 x 之上。扔这一次只花费了1个扔的次数，在这之后还可以向上确定dp[i][j-1]层。
dp[i][j] += dp[i][j-1]
另外，在 x 层扔的这一次本身也确定了一层。dp[j][j]还要+1
综上：
dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1
求dp，两边for循环枚举 i , j 即可。
AC Code：
// dp[i][j] = max num of decided floors
// i: num of burst balloons
// j: throwing times
// we can ammuse that we will use i balloons and throw them j times
// when throwing ith balloon at a certain floor:
// the num of floors we can still confirm:
// 1) burst: dp[i-1][j-1] (downstair)
// 2) intact: dp[i][j-1] (upstair)
// dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1
// ans = minimum j with the dp val not less than the height of the house #include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_K 105
#define INF 10000000 using namespace std; int k;
int ans;
long long n;
long long dp[MAX_K][MAX_K]; int main()
{
while(cin>>k>>n)
{
if(k==) break;
memset(dp,,sizeof(dp));
ans=INF;
for(int i=;i<=k;i++)
{
for(int j=;j<=;j++)
{
dp[i][j]=dp[i-][j-]+dp[i][j-]+;
if(dp[i][j]>=n) ans=min(ans,j);
}
}
if(ans==INF) cout<<"More than 63 trials needed."<<endl;
else cout<<ans<<endl;
}
}