d******e
发帖数: 164 | 1 A circus is designing a tower routine consisting of people standing atop one
another’s shoulders. For practical and aesthetic reasons, each person must
be both shorter and lighter than the person below him or her. Given the
heights and weights of each person in the circus, write a method to compute
the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56,
90)
(60,95) (65,100) (68,110) (70,150) (75,190)
这个问题给出的算法思路貌似不对？
比如说对于下面的输出：
(1, 2) (2, 3) (3, 9) (4, 5) (5, 6) (9, 4)
最大的输出应该是：
(1, 2) (2, 3) (4, 5) (5, 6)
请教这个问题如何解？ | g****y
发帖数: 240 | 2 先按照其中的一维排序，然后找另一维的longest increasing sequence | d******e
发帖数: 164 | 3 Why "longest increasing sequence"?
对于上面的例子，
(1, 2) (2, 3) (3, 9) (4, 5) (5, 6) (9, 4)
找出来的结果是：
(1, 2) (2, 3) (3, 9)
但显然存在更长的序列：
(1, 2) (2, 3) (4, 5) (5, 6)
【在 g****y 的大作中提到】
: 先按照其中的一维排序，然后找另一维的longest increasing sequence
| b***m
发帖数: 5987 | 4
longest increasing sequence并不要求连续啊。
【在 d******e 的大作中提到】
: Why "longest increasing sequence"?
: 对于上面的例子，
: (1, 2) (2, 3) (3, 9) (4, 5) (5, 6) (9, 4)
: 找出来的结果是：
: (1, 2) (2, 3) (3, 9)
: 但显然存在更长的序列：
: (1, 2) (2, 3) (4, 5) (5, 6)
|
|
