Uva10934 Dropping Water balloons 【Dp】

tonyfang posted @ 2016年7月29日 08:17 in uvaoj with tags c++ OI , 178 阅读

有一个n层楼高的楼房,可以从任意一层往下丢水球,这个水球有一个抗击打系数,表示它从最高多少层仍下去不会碎,问最多摔碎K次的情况下,你最少扔多少次能测出这个系数。

【题解】

转化模型,猜$[1, n]$内的数$Y$,每次猜一个$X$,你会得到回答$X>Y$或$X=Y$或$X>Y$。在最多猜k次$X>Y$的情况下,最少猜多少次才能猜对。

设f[i, j]表示用了i次询问,得到了j次$X>Y$的回答后游戏就会结束的情况下,最多测出多长。

$f[i,j] = f[i-1, j-1] + f[i-1, j] + 1$

那么就转移啦。

后面的答案就是找到最小的$ans$使得$f[ans][k] >= N$

 

// Uva Online Judge 10934
# include <stdio.h>
# include <algorithm>

using namespace std;

long long f[101][101];
int k;
long long n;

int main() {
	for (int i=1; i<=63; ++i)
		for (int j=1; j<=63; ++j)
			f[i][j] = f[i-1][j] + f[i-1][j-1] + 1;
	while(~scanf("%d%lld", &k, &n) && k) {
		int ans;
		k = min(63, k);
		bool ok=1;
		for (int i=0; i<=63; ++i)
			if(f[i][k] >= n) {
				ans = i;
				ok = 0;
				break;
			}
		if(ok) {
			puts("More than 63 trials needed.");
		} else {
			printf("%d\n", ans);
		}
	}
	return 0;
}

	

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter