Download presentation
Presentation is loading. Please wait.
1
10934 - Dropping water balloons
★★★★☆ 題組：Problem Set Archive with Online Judge 題號： Dropping water balloons 解題者：王振宇 解題日期：2014年5月1日 題意：某間大學他們打算向新生們丟水球.可是當他們充 好水之後發現, 這些水球太堅固了, 有時候連從很高的樓 層丟下來都不會破. 希望你幫他們找出至少要從第幾層樓 丟, 水球才會破掉. 可是偏偏你又很懶惰, 你希望花最少 次的試驗, 就知道水球會在哪一層樓丟下到地上剛好破掉 .題目會給你k(1≤k≤100)個水球,樓層高度n(int64), 你必 須回答最少要試幾次,才會知道水球會在哪一層樓丟下到 地上剛好破掉. 1
2
要在最糟糕的情况下（即最後一層才能摔破，但是你不 知道是最後一層），用最少的次數可以知道。 如果水球沒破，還可以繼續用此顆水球。
題意範例： 要在最糟糕的情况下（即最後一層才能摔破，但是你不 知道是最後一層），用最少的次數可以知道。 如果水球沒破，還可以繼續用此顆水球。 只有一個水球的情況下，你直接在正中間樓層放下去， 如果摔破的話，那麼你就沒有其它球繼續做實驗了。所 以你只能從第一層開始一直往上丟，第一個摔破的樓層 就是目標樓層了。所以最糟糕的情況下就是要做N次。 最少的次數就是用二元搜尋的方法：首先在正中間摔下 去，如果破的話，說明目標位置在下半部分，不破的話 說明是在上半部分。然後繼續在對應的部分再二分下去 。 2
3
解法：動態規劃+二元搜尋 解法範例： Ball k , Trial i 2
4
解法：動態規劃+二元搜尋 解法範例： Ball k , Trial i-1 Ball k , Trial i 1
2
5
解法：動態規劃+二元搜尋 解法範例： dp[ k ][ i-1 ] dp[ k ][ i ] 1 dp[ k-1 ][ i-1 ] 2
![解法：動態規劃+二元搜尋 解法範例： dp[ k ][ i-1 ] dp[ k ][ i ] 1 dp[ k-1 ][ i-1 ] 2](http://slidesplayer.com/slide/11358697/61/images/5/%E8%A7%A3%E6%B3%95%EF%BC%9A%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%2B%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B+%E8%A7%A3%E6%B3%95%E7%AF%84%E4%BE%8B%EF%BC%9A+dp%5B+k+%5D%5B+i-1+%5D+dp%5B+k+%5D%5B+i+%5D+1+dp%5B+k-1+%5D%5B+i-1+%5D+2.jpg "解法：動態規劃+二元搜尋 解法範例： dp[ k ][ i-1 ] dp[ k ][ i ] 1 dp[ k-1 ][ i-1 ] 2")
6
dp[ k ][ i ] = dp[ k ][ i-1 ] + 1 + dp[ k-1 ][ i-1 ]
討論： dp[ k ][ i ] = dp[ k ][ i-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
![dp[ k ][ i ] = dp[ k ][ i-1 ] dp[ k-1 ][ i-1 ]](http://slidesplayer.com/slide/11358697/61/images/6/dp%5B+k+%5D%5B+i+%5D+%3D+dp%5B+k+%5D%5B+i-1+%5D+dp%5B+k-1+%5D%5B+i-1+%5D.jpg "討論： dp[ k ][ i ] = dp[ k ][ i-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.")
Similar presentations
