马戏团（动态规划）---搜狐2016研发工程师编程题

时间：2022-08-07 11:13:01

[编程题] 马戏团 搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。

输入描述:
首先一个正整数N，表示人员个数。 
之后N行，每行三个数，分别对应马戏团员编号，体重和身高。


输出描述:
正整数m，表示罗汉塔的高度。

输入例子:
6
1 65 100
2 75 80
3 80 100
4 60 95
5 82 101
6 81 70

输出例子:
4

动态规划，用到了最长上升子序列问题。首先按照体重从小到大排序，体重相同时，身高高的在上，然后求最长身高上升子序列的长度。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

struct node {
int w;
int h;
node(int _w, int _h) : w(_w), h(_h) {}
};

bool cmp(node first, node next) {
if (first.w != next.w) {
return first.w < next.w;
}
else {
return first.h > next.h;
}
}

int main() {
int input;

while (cin >> input) {
int num, w, h;
vector<node> vec;
for (int i = 0; i < input; ++i) {
cin >> num >> w >> h;
node tmp(w, h);
vec.push_back(tmp);
}

stable_sort(vec.begin(), vec.end(), cmp);

vector<int> dq(input + 1, 0);
dq[0] = 1;
for (int i = 0; i < input; ++i) {
dq[i] = 1;
for (int j = 0; j < i; ++j) {
if (vec[j].h <= vec[i].h && dq[j] + 1 >= dq[i]) {
dq[i] = dq[j] + 1;
}
}
}

int max = 0;
for (int i = 0; i < dq.size(); ++i) {
if (max < dq[i]) max = dq[i];
}

cout << max << endl;
}

return 0;
}

  • 枯萎的海风：你好， 我调试了一天终于发现自己的代码是在排序的时候出了问题， 我是按照体重从小到大排序， 相同题中条件下， 将身高高的放在后面， 而你的是放在了前面， 我很困惑为什么是相同体重的身高高的应该放前面呢， 谢谢2016-01-02 19:35:01回复赞(2)
  • 613何回复 枯萎的海风：我也遇到和你一样的问题，身高高的放在后面明显层数更高，总感觉题目测试用例答案就是错的2016-01-08 18:12:21回复赞(0)
  • 枯萎的海风回复 613何：对啊， 就是这个问题， 死活通不过， 特蛋疼2016-01-08 21:56:10回复赞(0)
  • 咕米乐回复 枯萎的海风：如果首先按照体重递减来排列，再从末尾开始沿着身高递增来动态归化，如果在体重相等时按照身高递减排列，在最后会将所有体重相等的情况都计划进去，所以那样的话当体重相等时不能达到动态规划的选择效果。
    W 100 90 90 90 W 100 90 90 90
    H 80 70 80 90 H 80 90 80 70
    对比一下就会发现    2016-03-08 21:45:01回复赞(0)
  • Azusa回复 枯萎的海风：我也是这个问题，还没想明白是为什么2016-03-20 15:36:30回复赞(1)
  • jesonlin：我也不明白在体重递增情况下如果相同体重，应该是身高高的放在后面这样高度更大吧2016-03-22 11:54:04回复赞(2)
  • me_wm回复 jesonlin：根据题意，“站在某个人肩上的人应该既比自己矮又比自己瘦，或相等”，因此只比自己矮或瘦的不应该站在自己肩上，如果身高高的排在后面，则跟自己相同体重，比自己矮的人会站到自己肩上，不符合题意，所以把相同体重下，身高高的放在前面，这样动态规划计数时就不会计入叠罗汉队列。2016-03-23 10:39:25回复已赞(3)
  • jesonlin回复 me_wm：动态规划我是按照最长不下降子序列的思想来得，从前往后遍历，体重相同，身高高的在后面会获得更长的子序列，不会出现矮的人站在高的前面2016-03-24 09:46:45回复赞(0)
  • 逗比豪：照这种方法做，如果输入第一个人100斤 100cm 第二个人101斤 200cm 第三个人 102 101cm 第四个人103 102cm ……后面只要是身高小于第二个人的200cm都会被舍去，得到的最高序列为2。实际上必须得把第二个人给舍去才对2016-03-24 21:24:08回复赞(1)
  • 董泽锋回复 me_wm：题目都没说清楚， 搞死人。 我理解的是， 比自己矮，相同体重的人可以站自己肩上啊2016-06-24 19:57:13回复赞(0)

第二次做：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std ;

struct node {
   int w ;
   int h ;
} ;

bool cmp( node first, node next ) {
    if ( first.w != next.w ) {
        return first.w < next.w ;
    } else {
        return first.h > next.h ;
    }
}

int main() {
    int input ;

    while ( cin >> input ) {
        vector<node> vec ;
        for ( int i = 0; i < input; ++ i ) {
            int num, w, h ;
            cin >> num >> w >> h ;
            node tmp ;
            tmp.w = w ;
            tmp.h = h ;
            vec.push_back( tmp ) ;
        }

        stable_sort( vec.begin(), vec.end(), cmp ) ;

        vector<int> dq( input + 1, 0 ) ;
        dq[0] = 1 ;
        for ( int i = 0; i < input; ++ i ) {
            dq[i] = 1 ;
            for ( int j = 0; j < i; ++ j ) {
                if ( vec[j].h <= vec[i].h && dq[j] + 1 > dq[i] ) {
                    dq[i] = dq[j] + 1 ;
                }
            }
        }

        int max = 0 ;
        for ( int i = 0; i < input; ++ i ) {
            if ( max < dq[i] ) max = dq[i] ;
        }

        cout << max << endl ;
    }

    return 0 ;
}


第三次做：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std ;

struct node {
   int w ;
   int h ;
} ;

bool cmp( node first, node next ) {
    if ( first.w != next.w ) return first.w < next.w ;
    else return first.h > next.h ;
}

int main() {
    int n ;

    while ( cin >> n ) {
        if ( n <= 0 ) break ;

        vector<node> vec ;
        for ( int i = 0; i < n; ++ i ) {
            int num, weight, height ;
            cin >> num >> weight >> height ;
            node tmp ;
            tmp.w = weight ;
            tmp.h = height ;
            vec.push_back( tmp ) ;
        }

        stable_sort( vec.begin(), vec.end(), cmp ) ;

        vector<int> liss( n + 1, 1 ) ;
        int max = 0 ;
        for ( int i = 0; i < n; ++ i ) {
            for ( int j = 0; j < i; ++ j ) {
                if ( vec[j].h <= vec[i].h && liss[j] + 1 > liss[i] ) {
                    liss[i] = liss[j] + 1 ;
                    if ( max < liss[i] ) max = liss[i] ;
                }
            }
        }

        cout << max << endl ;
    }

    return 0 ;
}


标签：

相关文章