題目鏈接： uva-10934 題意 你有k個一模一樣的水球，在一個n層樓的建築物上進行測試，你想知道水球最低從幾層樓往下丟可以讓水球破掉。由於你很懶，所以你想要丟最少次水球來測出水球剛好破掉的最低樓層。（在最糟情況下，水球在頂樓也不會破）你可以在某一層樓丟下水球來測試，如果水球沒破，你可以再撿起來繼續用。 Input 輸入的每一行包含多組測試，每組測試為一行。每組測試包含兩個整數 k 和 n， 1 <= k <= 100 而 n 是一個 64 位的整數（沒錯，這棟建築物的確很高），最後一組k = 0，n=0 代表結束，這組測試不用處理。 Output 對於每次測試，輸出在最糟情況下，測出水球破掉樓層的最少次數。如果他多於63次，就輸出“More than 63 trials needed.” 思路 題目已經說得很清楚了，要在最糟糕的情況下（即最後一層才能摔破，但是你不知道是最後一層），用最少的次數可以知道。 在假設你有無數個水球的情況下，那麼最少的次數肯定就是用二分的方法：首先在正中間摔下去，如果破的話，說明目標位 置在下半部分，不破的話說明是在上半部分。上後繼續在對應的部分再二分下去……需要logn次。 但是這題的水球數量有限，例如，只有一個水球的情況下，你直接在正中間樓層放下去，如果摔破的話，那麼你就沒有其它 球繼續做實驗了。所以你只能從第一層開始一直往上丟，第一個摔破的樓層就是目標樓層了。那麼最糟糕的情況下就是要做N次。 這樣的話還是不太好想，所以要把問題轉換一下，變成：“給k個氣球，丟j次，最多能確定第幾層？” 這樣，就可以用f(i, j)狀態來表示第i個氣球，丟j次最多確定的層數。 對於f(i, j), 我們不知道它最多可以確定第幾層，假設第一次在x層仍球，如果球破了，那麼我們花費了一個球和仍了一次的費用， 我們可以知道f(i-1, j-1)可以確定的層數，那麼就可以確定x = f(i-1, j-1) + 1。 如果在x層時如果球沒有破，那麼我們只花費了仍一次的費用，還剩下i個球，j-1次可以用，那麼用這些可以確定的層數f(i, j-1) 所以，得到遞推式，推出最高能確定的層數： f(i, j) = f(i-1, j-1) + 1 + f(i, j-1); 代碼
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**=====================================================
* This is a solution for ACM/ICPC problem
*
* @source : uva-10934 Dropping water balloons
* @description : dp
* @author : shuangde
* @blog : blog.csdn.net/shuangde800
* @email : zengshuangde@gmail.com
* Copyright (C) 2013/09/09 12:49 All rights reserved.
*======================================================*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
int64 f[110][65];
inline void init() {
memset(f, 0, sizeof(f));
for (int i = 1; i < 64; ++i) {
for (int j = 1; j < 64; ++j) {
f[i][j] = f[i][j-1] + f[i-1][j-1] + 1;
}
}
}
int main(){
init();
int k;
int64 n;
while (~scanf("%d%lld", &k, &n) && k) {
k = min(63, k);
bool ok = false;
for (int i = 0; i <= 63; ++i) {
if (f[k][i] >= n) {
printf("%d\n", i);
ok = true;
break;
}
}
if (!ok) puts("More than 63 trials needed.");
}
return 0;
}
來自CODE的代碼片
