10934 - Dropping water balloons ★★★★☆ 題組：Problem Set Archive with Online Judge 題號：10934 - Dropping water balloons 解題者：王振宇 解題日期：2014年5月1日 題意：某間大學他們打算向新生們丟水球.可是當他們充 好水之後發現, 這些水球太堅固了, 有時候連從很高的樓 層丟下來都不會破. 希望你幫他們找出至少要從第幾層樓 丟, 水球才會破掉. 可是偏偏你又很懶惰, 你希望花最少 次的試驗, 就知道水球會在哪一層樓丟下到地上剛好破掉 .題目會給你k(1≤k≤100)個水球,樓層高度n(int64), 你必 須回答最少要試幾次,才會知道水球會在哪一層樓丟下到 地上剛好破掉. 1
要在最糟糕的情况下（即最後一層才能摔破，但是你不 知道是最後一層），用最少的次數可以知道。 如果水球沒破，還可以繼續用此顆水球。 題意範例： 要在最糟糕的情况下（即最後一層才能摔破，但是你不 知道是最後一層），用最少的次數可以知道。 如果水球沒破，還可以繼續用此顆水球。 只有一個水球的情況下，你直接在正中間樓層放下去， 如果摔破的話，那麼你就沒有其它球繼續做實驗了。所 以你只能從第一層開始一直往上丟，第一個摔破的樓層 就是目標樓層了。所以最糟糕的情況下就是要做N次。 最少的次數就是用二元搜尋的方法：首先在正中間摔下 去，如果破的話，說明目標位置在下半部分，不破的話 說明是在上半部分。然後繼續在對應的部分再二分下去 。 2
解法：動態規劃+二元搜尋 解法範例： Ball k , Trial i 2
解法：動態規劃+二元搜尋 解法範例： Ball k , Trial i-1 Ball k , Trial i 1 2
解法：動態規劃+二元搜尋 解法範例： dp[ k ][ i-1 ] dp[ k ][ i ] 1 dp[ k-1 ][ i-1 ] 2
dp[ k ][ i ] = dp[ k ][ i-1 ] + 1 + dp[ k-1 ][ i-1 ] 討論： dp[ k ][ i ] = dp[ k ][ i-1 ] + 1 + dp[ k-1 ][ i-1 ] floor number : 64-bit int => use unsigned long long 只有一顆水球時 : dp[ 1 ][ n ] = n 求解時：Given k,n 找出最小i 滿足 dp[ k ][ i ] = n 2