Google : 马戏团人塔问题

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)

算简单的吧

Similar to longest increasing subsequence. Sort element. Then for each person at index i, find the person whose height and weight is smaller but with largest score s. Then the person at index i score s+1; track each person's previous person's idx for final printing.

        public static void maxLength(List a){
        // using dynamic programming.
                // similar to longest increasing subsequence.
               
                // sort array first, takes O(nlogn)
                Collections.sort(a);
               
                // use an array to track the idx of  ...
hkgzyx 发表于 2011-6-13 07:36

    我没仔细看代码，你测试过觉得可行吗？或者再详细说说算法？？
    不是很懂JAVA,这个Collections.sort 是根据什么来排序的？

给出个我的解法：
1. 对每个人的高度排序，为A列
2. 对每个人的体重排序，为B列
3. 找出A,B的最大公共子序列，为C,

C即为答案

wwwyhx 发表于 2011-6-13 20:33
给出个我的解法：
1. 对每个人的高度排序，为A列
2. 对每个人的体重排序，为B列

最长上升子序列，对高度排序然后对排序后的数组X找出按体重的最长上升子序列即可。时间复杂度O(nlogn)。
楼主这个解法也是正确的，可以证明AB的任一公共子序列都是X的上升子序列，且X的任一上升子序列都是AB的公共子序列。但是这个解法需要O(n^2)。