Total Submissions:3577 Solved:648
Time Limit: 3000 mSec
Problem Description
It’s frosh week, and this year your friends have decided that they would initiate the new computer science students by dropping water balloons on them. They’ve filled 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 bursting! 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 floor from which they can drop the balloons so that they do burst. You know the building has n floors, and your friends have given you k identical balloons which you may use (and break) during your trials to find their answer. 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 floor 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 floor). A trial consists of dropping a balloon from a certain floor. 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 fits into a 64 bit integer (yes, it’s a very tall building). The last case has k = 0 and should not be processed.
Output
Sample Input
Sample Output
14
21
More than 63 trials needed.
61
63
题解：这个题属于比较经典的动态规划题，dp(i,j)表示i个水球，做j次实验能够测出的最高楼层，考虑第一个水球，将其在第k层扔下，如果炸了，那就说明硬度<k，为了能够在剩下的i-1个水球和j-1次实验机会中测出硬度，必须要求k-1<=dp(i-1,j-1),也就是说k最大dp(i-1,j-1)+1,如果没炸，那么k+1层相当于新的1层，还有i个球，j-1次机会，能够测到的楼层自然是dp(i-1,j)，因此加上前面的，就是总共能测得最高的。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = + ; int k;
LL n, dp[maxn][]; LL DP(int k, int i) {
if (dp[k][i] > ) return dp[k][i];
if (!k || !i) return dp[k][i] = ; return dp[k][i] = DP(k - , i - ) + DP(k, i - ) + ;
} int main()
{
//freopen("input.txt", "r", stdin);
memset(dp, -, sizeof(dp));
while (~scanf("%d%lld", &k, &n) && k) {
int i;
for (i = ; i <= ; i++) {
if (DP(k, i) >= n) {
printf("%d\n", i);
break;
}
}
if (i == ) printf("More than 63 trials needed.\n");
}
return ;
}