Uva10934 Dropping Water balloons 【Dp】

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

有一个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;
}

	
RNFI Login 说:
2022年11月09日 19:22

Online money transactions offer security and ease of transfer, reducing the fear of theft. The tech industry has developed significant platforms to help in digital financial transactions. RNFI Login RNFI is an exclusive digital transfer service designed to help retailers, distributors, and users send and receive money online. The RNFI offers several rewards to users (B2B) for conducting financial transactions using the platform.

Khajane 2 Login 说:
2023年1月23日 14:50

K2 challan also referred to as Khajane 2, an integrated financial management system from the Government of Karnataka. The K2 has been brought into working with an aim to manage the financial business of the government. Khajane 2 Login It works to simplify the process of remittance of departments under government by bringing an option of anywhere-anytime payment options. Firstly every department under the government of Karnataka will have access to Khajane 2 which allows their customers to remit to the government through the easy payment links provided.

pscmodelpapers.in 说:
2023年4月19日 16:20

PSC Model Papers 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. pscmodelpapers.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


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