It’s frosh week, and this year your friends have decided that they
would initiate the new computer science students by drop- ping water
balloons on them. They’ve lled up a large crate of identical water
balloons, ready for the event. But as fate would have it, the balloons
turned out to be rather tough, and can be dropped from a height of
several stories without burst- ing! So your friends have sought you
out for help. They plan to drop the balloons from a tall building on
campus, but would like to spend as little effort as possible hauling
their balloons up the stairs, so they would like to know the lowest
oor from which they can drop the balloons so that they do burst. You
know the building has n oors, and your friends have given you k iden-
tical balloons which you may use (and break) during your trials to nd
their an- swer. Since you are also lazy, you would like to determine
the minimum number of trials you must conduct in order to determine
with absolute certainty the lowest oor from which you can drop a
balloon so that it bursts (or in the worst case, that the balloons
will not burst even when dropped from the top oor). A trial consists
of dropping a balloon from a certain oor. If a balloon fails to burst
for a trial, you can fetch it and use it again for another trial.
Input The input consists of a number of test cases, one case per line.
The data for one test case consists of two numbers k and n , 1 k
100 and a positive n that ts into a 64 bit integer (yes, it’s a very
tall building). The last case has k
= 0 and should not be processed. Output For each case of the input, print one line of output giving the minimum number of trials needed to
solve the problem. If more than 63 trials are needed then print ` More
than 63 trials needed. ’ instead of the number.
如果用dp[i][j]表示i个球j层楼的试验次数，显然时间和空间都无法承受。
因为楼层数比较大，考虑把它作为数组里存的数。用dp[i][j]表示i个气球试j次能测的最高楼层，分为这一次摔碎没有，dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1
#include<cstdio>
#define LL long long
const int maxn=100,maxm=63;
LL dp[maxn+5][maxm+5];
int main()
{int i,j,k,m,n,p,q;LL x,y,z;for (i=1;i<=maxn;i++)for (j=1;j<=maxm;j++)dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+1;while (scanf("%d%lld",&n,&x)&&n){for (i=1;i<=maxm;i++)if (dp[n][i]>=x){printf("%d\n",i);break;}if (i>maxm) printf("More than 63 trials needed.\n");}
}