作者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
1F：推 legendmtg:走错版罗 该去Prob_Solve 04/26 02:47
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.88.191
2F：推 sunneo:贪婪演算法 + backtracking如何 ? 04/27 00:22
3F：→ sunneo:感觉上蛮像是avltree调整高度的感觉 04/27 00:24
4F：→ sunneo:由力量最大的里面挑出(力量 - 体重)最大的 04/27 00:27
5F：推 chienmin18:我用楼上的方法greedy下去WA 04/27 01:03
6F：→ chienmin18:去讨论区看有抓到导致错误的测资 04/27 01:04
7F：→ chienmin18:好像还是要DP解吧 04/27 01:04
8F：→ revivalworld:我资工系的室友昨天也在写这题 一模一样 04/27 15:23
9F：→ revivalworld:该不会是同个老师吧 XD 04/27 15:24
10F：推 bafu:DP(LIS) :) 04/27 17:55
11F：推 march20:有 DP 的感觉 04/29 07:27