題目鏈接： 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 : [email protected] * 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的代碼片
