哇楠哥居然当了歌王阿 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>TVChinese - 中文电视

哇楠哥居然当了歌王阿

哇楠哥居然当了歌王阿# TVChinese - 中文电视

K*g2015-08-11 07:08

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上的解答，请问谁能详细点给出答案呢，多谢了

g*u2015-08-11 07:08

2 楼

这么有辨识度的情况下拿下了第三期歌王？
实力阿

l*a2015-08-11 07:08

3 楼

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*72015-08-11 07:08

4 楼

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*k2015-08-11 07:08

5 楼

I don't think career cup gives the right answer for the 2nd step.

h*g2015-08-11 07:08

6 楼

有一个问题：
如果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 的大作中提到】

s*x2015-08-11 07:08

7 楼

me either. apparently is not correct.

【在 x****k 的大作中提到】

: I don't think career cup gives the right answer for the 2nd step.

P*l2015-08-11 07:08

8 楼

有相同的为什么不能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*l2015-08-11 07:08

9 楼

因为要lighter and shorter，所以某一项相等是不行的

【在 P**l 的大作中提到】

: 有相同的为什么不能lis?

d*l2015-08-11 07:08

10 楼

我觉得可以对LIS的算法做些修改，这里要用那个LIS的O(n^2)算法。因为height相同的
所有人最多只有一个被取出来，所以在比较更新LIS的时候略过和当前height一样的那
些人就行。原始方法大概是这样
for(i=0;ifor(j=0;jif(weight[j]dp[i]=max(dp[i],dp[j]+1);
修改后的方法：
for(i=0;ifor(j=0;jif(height[j]>=height[i]) break;
if(weight[j]dp[i]=max(dp[i],dp[j]+1);
这样就能保证取出的最长上升序列中没有两个的height是相同的。

【在 h*****g 的大作中提到】

P*l2015-08-11 07:08

11 楼

哦

【在 d*******l 的大作中提到】

: 因为要lighter and shorter，所以某一项相等是不行的