[最长非升子序列+nlog(n)]北大 POJ 3636 Nested Dolls
2012-07-09 16:01:06

[cpp]
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

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;