作者richard730 (Life Bubble GT)
看板Prob_Solve
標題[問題] 烏龜塔
時間Sun Apr 26 13:05:24 2009
※ [本文轉錄自 CSSE 看板]
作者: richard730 (Life Bubble GT) 看板: CSSE
標題: [問題] 烏龜塔
時間: Sun Apr 26 00:54:38 2009
(程式題) 許多人都看過烏龜1隻再疊上1隻，如同1個烏龜塔的樣子，想當然耳，在最下方
的烏龜，會承受最多的重量。由於每隻烏龜在體重及力量上都有所不同，因此不同的擺放
次序，會影響到烏龜塔的高度。現在，你的任務是盡你所能，疊出最高的烏龜塔。
輸入：
標準輸入包含了許多行，每行擁有一對以一個或多個空白分開的整數，代表烏龜的體重及
力量。烏龜體重的單位是公克，力量是烏龜全部能負擔的重量，包括它自己的體重，單位
同樣也是公克。因此，1隻體重300公克，力量1000公克的烏龜，可以在自己背上負擔總重
700公克的烏龜 (可以有好幾隻)。烏龜最多只有5607隻。
輸出：
只要輸出一行內含最高烏龜塔的高度。以下是一個輸出入的實例:
Sample Input
300 1000
1000 1200
200 600
100 101
Sample Output for the Sample Input
3
題目大致上是這樣
請問高手們有什麼想法提供給小弟嗎?
感激不盡
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.88.109
推 legendmtg:走錯版囉 該去Prob_Solve 04/26 02:47
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.88.191
推 sunneo:貪婪演算法 + backtracking如何 ? 04/27 00:22
→ sunneo:感覺上蠻像是avltree調整高度的感覺 04/27 00:24
→ sunneo:由力量最大的裡面挑出(力量 - 體重)最大的 04/27 00:27
推 chienmin18:我用樓上的方法greedy下去WA 04/27 01:03
→ chienmin18:去討論區看有抓到導致錯誤的測資 04/27 01:04
→ chienmin18:好像還是要DP解吧 04/27 01:04
→ revivalworld:我資工系的室友昨天也在寫這題 一模一樣 04/27 15:23
→ revivalworld:該不會是同個老師吧 XD 04/27 15:24
推 bafu:DP(LIS) :) 04/27 17:55
推 march20:有 DP 的感覺 04/29 07:27