uva 10934 - Dropping water balloons(dp)

题目链接：uva 10934 - Dropping water balloons

题目大意：给出k和n，表示说有k个相同的水球，和一个高度为n的楼房，然后水球从某一层丢下会破，问说最少丢几次才可以测量出该高度。

解题思路：很容易会想到说二分，但是注意二分的话不一定最优，因为水球的数量有限，如果没破的话可以继续使用，但是破了的话就不能用了，如果只剩一个水球，就得从最小层开始一层一层向上。

dp[i][j]表示i个水球丢j次可以测量的最大高度。

dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1.分别为碎了和没碎的可能。

处理完dp数组，每次只要找到一个最小的j，使得dp[k][j] ≥ n，即可。

#include <stdio.h>
#include <string.h>

const int N = 105;
typedef long long ll;

int k;
ll n, dp[N][N];

void init () {
	memset(dp, 0, sizeof(dp));

	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= 63; j++)
			dp[i][j] = dp[i][j-1] + dp[i-1][j-1]+1;
	}
}

bool judge () {

	for (int i = 1; i <= 63; i++) {
		if (dp[k][i] >= n) {
			printf("%d\n", i);
			return true;
		}
	}
	return false;
}

int main () {
	init ();
	while (scanf("%d%lld", &k, &n) == 2 && k && n) {
		if (!judge()) printf("More than 63 trials needed.\n");
	}
	return 0;
}

uva 10934 - Dropping water balloons(dp),布布扣,bubuko.com

uva 10934 - Dropping water balloons(dp)

原文：http://blog.csdn.net/keshuai19940722/article/details/22159641