K******g
发帖数: 1870 | 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.
我没有看懂careercup上的解答，请问谁能详细点给出答案呢，多谢了 | l*****a
发帖数: 14598 | 2 I remember that,the answer there is really not clear.
step 1) sort by height O(nlogn)
step 2) find the longest increase sequence O(nlogn) by weight
there is tricky in step 2).
but LIS should be a common issue
one
【在 K******g 的大作中提到】
: 请问有谁看懂了这道题
: 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.
| p********7
发帖数: 549 | 3 this is the right answer
【在 l*****a 的大作中提到】
: I remember that,the answer there is really not clear.
: step 1) sort by height O(nlogn)
: step 2) find the longest increase sequence O(nlogn) by weight
: there is tricky in step 2).
: but LIS should be a common issue
:
: one
| x****k
发帖数: 2932 | 4 I don't think career cup gives the right answer for the 2nd step. | h*****g
发帖数: 312 | 5 有一个问题：
如果height有几个值是相同的，比如下面的65，该怎么办？
(56, 90) (65,95) (65,10) (68,110) (70,150) (75,190)
my idea:
if you find some heights have the same value,
1. firstly remove others except the first one among them, and find LIS
2. remove others except the second one among them, and find LIS
3......
4...
最后 再比较取 最大的LIS.
但感觉这样做好麻烦~ 如果有2个65， 3个68，就要find 6次LIS.
各位有没有好点儿的idea?
【在 l*****a 的大作中提到】
: I remember that,the answer there is really not clear.
: step 1) sort by height O(nlogn)
: step 2) find the longest increase sequence O(nlogn) by weight
: there is tricky in step 2).
: but LIS should be a common issue
:
: one
| s**x
发帖数: 7506 | 6 me either. apparently is not correct.
【在 x****k 的大作中提到】
: I don't think career cup gives the right answer for the 2nd step.
| P**l
发帖数: 3722 | 7 有相同的为什么不能lis?
【在 h*****g 的大作中提到】
: 有一个问题：
: 如果height有几个值是相同的，比如下面的65，该怎么办？
: (56, 90) (65,95) (65,10) (68,110) (70,150) (75,190)
: my idea:
: if you find some heights have the same value,
: 1. firstly remove others except the first one among them, and find LIS
: 2. remove others except the second one among them, and find LIS
: 3......
: 4...
: 最后 再比较取 最大的LIS.
| d*******l
发帖数: 338 | 8 因为要lighter and shorter，所以某一项相等是不行的
【在 P**l 的大作中提到】
: 有相同的为什么不能lis?
| d*******l
发帖数: 338 | 9 我觉得可以对LIS的算法做些修改，这里要用那个LIS的O(n^2)算法。因为height相同的
所有人最多只有一个被取出来，所以在比较更新LIS的时候略过和当前height一样的那
些人就行。原始方法大概是这样
for(i=0;i
for(j=0;j
if(weight[j]
dp[i]=max(dp[i],dp[j]+1);
修改后的方法：
for(i=0;i
for(j=0;j
if(height[j]>=height[i]) break;
if(weight[j]
dp[i]=max(dp[i],dp[j]+1);
这样就能保证取出的最长上升序列中没有两个的height是相同的。
【在 h*****g 的大作中提到】
: 有一个问题：
: 如果height有几个值是相同的，比如下面的65，该怎么办？
: (56, 90) (65,95) (65,10) (68,110) (70,150) (75,190)
: my idea:
: if you find some heights have the same value,
: 1. firstly remove others except the first one among them, and find LIS
: 2. remove others except the second one among them, and find LIS
: 3......
: 4...
: 最后 再比较取 最大的LIS.
| P**l
发帖数: 3722 | 10 哦
【在 d*******l 的大作中提到】
: 因为要lighter and shorter，所以某一项相等是不行的
|
|
