/* THE PROGRAM IS MADE BY PYY */?
/*----------------------------------------------------------------------------//
??? Copyright (c) 2012 panyanyany All rights reserved.
?
??? URL?? : http://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
#include
#include
#include
#include
?
#include
#include
#include
#include
#include
?
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;?
}?
?
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