i********s
发帖数: 133 | 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) | g*******s
发帖数: 490 | 2 第2步就是典型的dynamic programming
a[0].....a[n]
j->0,n, 对于每个状态j,找到以a[j]结尾的largest increasing sequence.
然后状态j+1怎么得到，比较a[j+1] with a[0]...a[j], if a[j+1] > a[i] and a[i]
has the largest increasing sequence among a[0]...a[j], the largest increasing
sequence for 状态j+1 = the largest increasing
sequence for 状态 i + a[j+1]
至于career cup上的第2步做法也是对的，就是了 |
|
