频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
[最长非升子序列+nlog(n)]北大 POJ 3636 Nested Dolls
2012-07-09 16:01:06           
收藏   我要投稿
[cpp] 
/* THE PROGRAM IS MADE BY PYY */ 
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.
 
    URL   : https://poj.org/problem?id=3636
    Name  : 3636 Nested Dolls – 最长非升子序列
 
    Date  : Monday, July 9, 2012
    Time Stage : two hours
 
    Result:
10404790    panyanyany
3636
Accepted    400K    157MS   C++
1827B   2012-07-09 11:01:39
 
Test Data :
 
Review 
 www.2cto.com
//----------------------------------------------------------------------------*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <vector> 
 
#include <algorithm> 
#include <iostream> 
#include <queue> 
#include <set> 
#include <string> 
 
using namespace std ; 
 
#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value 
#define max(x, y)        ((x) > (y) ? (x) : (y)) 
#define min(x, y)        ((x) < (y) ? (x) : (y)) 
 
#define INF     (0x3f3f3f3f) 
#define MAXN    20009 
 
#define L(x)    ((x)<<1) 
#define R(x)    (((x)<<1)|1) 
#define M(x, y) (((x)+(y)) >> 1) 
 
#define DB    // 
 
struct NODE { 
    int w, h; 
}; 
 
bool cmp(const NODE &lhs, const NODE &rhs) 

    if (lhs.w == rhs.w) 
        return lhs.h > rhs.h; 
    return lhs.w < rhs.w; 

 
int order[MAXN]; 
NODE a[MAXN]; 
 
int LNotIncS(NODE a[], int n) 

    int i, r, l, len, m; 
 
    MEM(order, 0); 
    sort(a, a+n, cmp); 
 
    len = 1; 
 
    for (i = 0; i < n; ++i) 
    { 
        r = len; 
        l = 1; 
        while (l <= r) 
        { 
            m = (l + r) >> 1; 
            if (order[m] >= a[i].h) 
            { 
                l = m + 1; 
            } 
            else 
                r = m - 1; 
        } 
 
        // 更新有序表里面的长度为 L 的最大值. 
        // 如果有序表是上升的,则更新的是最小值 
        if (order[l] < a[i].h) 
            order[l] = a[i].h; 
        len = max(len, l); 
    } 
 
    return len; 

 
int main() 

    int i, tcase, n; 
    while (scanf("%d", &tcase) != EOF) 
    { 
        while (tcase--) 
        { 
            scanf("%d", &n); 
            for (i = 0; i < n; ++i) 
            { 
                scanf("%d %d", &a[i].w, &a[i].h); 
            } 
            printf("%d\n", LNotIncS(a, n)); 
        } 
    } 
    return 0; 

作者:panyanyany
点击复制链接 与好友分享!回本站首页
相关TAG标签 升子 序列 北大
上一篇:[最长下降子序列]北大 POJ 1065 Wooden Sticks
下一篇:POJ 1637 混合图欧拉回路的判定
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站