s********a
发帖数: 2796 | 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.
解答说是先按高度排序，然后重量排序。
那如果Input(ht, wt): (60, 200) (70, 150) (56, 90) (75, 190) (60, 95) (68,
110)
排序结果是（56，90）（60，95）（60，200）（68，110）（70，150）(75,190)
再按照解答的方法找最大序列，那么结果是3.
但是如果把（60，200）从序列中抽出去，结果不是能到5么？ | i*******r
发帖数: 51 | 2 先按第一项排序，再找第二项最长递增子列
one
must
compute
【在 s********a 的大作中提到】
: 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.
: 解答说是先按高度排序，然后重量排序。
: 那如果Input(ht, wt): (60, 200) (70, 150) (56, 90) (75, 190) (60, 95) (68,
: 110)
: 排序结果是（56，90）（60，95）（60，200）（68，110）（70，150）(75,190)
: 再按照解答的方法找最大序列，那么结果是3.
| s********a
发帖数: 2796 | 3 在上面这个例子中，如果把第二项中违反增长的那个去掉不更好么？
【在 i*******r 的大作中提到】
: 先按第一项排序，再找第二项最长递增子列
:
: one
: must
: compute
| b*******g
发帖数: 57 | 4 结果是5，动态规划一下就行了
与longest increasing sequence类似，sequence不一定是连续的
one
must
compute
【在 s********a 的大作中提到】
: 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.
: 解答说是先按高度排序，然后重量排序。
: 那如果Input(ht, wt): (60, 200) (70, 150) (56, 90) (75, 190) (60, 95) (68,
: 110)
: 排序结果是（56，90）（60，95）（60，200）（68，110）（70，150）(75,190)
: 再按照解答的方法找最大序列，那么结果是3.
|
|
