a261 - 10934 - Dropping water balloons

🔗 前往 ZeroJudge 原題

題目描述

題目要求在 n 層樓的建築物中，使用 k 個水球找到水球剛好會破掉的最低樓層，並在最壞情況下最小化測試次數。

解題思路

這題可以使用動態規劃來預先計算不同水球數量和樓層數下，最壞情況下的測試次數。dp[i][j] 表示使用 i 個水球測試 j 層樓所需的最少次數。狀態轉移方程為 dp[i][j] = dp[i-1][j-1] + 1 + dp[i-1][j]，其中 dp[i-1][j-1] + 1 表示在第 j 層樓丟水球，水球破掉的情況，需要 dp[i-1][j-1] 次測試剩下的 j-1 層樓，再加上本次的測試；dp[i-1][j] 表示在第 j 層樓丟水球，水球沒破的情況，需要 dp[i-1][j] 次測試剩下的 j 層樓。 預計算完 dp 陣列後，對於每組輸入的 k 和 n，我們從 dp[1][k] 開始尋找，找到第一個滿足 dp[i][k] >= n 的 i，即為答案。如果找不到，則輸出 "More than 63 trials needed."。

複雜度分析

• 時間複雜度: O(64 * 100 + T)，其中 T 是測試案例的數量。預計算 dp 陣列需要 O(64 * 100) 的時間，對於每個測試案例，尋找答案需要 O(64) 的時間。
• 空間複雜度: O(64 * 100)，用於儲存 dp 陣列。

程式碼

#include <iostream>
using namespace std;
long long dp[64][105],n,k;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	for(int i=1;i<=63;++i)
		for(int j=1;j<=100;++j)
			dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j];
	while(cin >> k >> n){
		if(k==0)return 0;
		bool ac=0;
		for(int i=1;i<=63;++i)
			if(dp[i][k]>=n){
				ac=1;
				cout << i << "\n";
				break;
			}
		if(ac==0)
			cout << "More than 63 trials needed.\n";
	}
}