[cpp]?
/* THE PROGRAM IS MADE BY PYY */?
/*----------------------------------------------------------------------------//
??? Copyright (c) 2012 panyanyany All rights reserved.
?
??? URL?? : http://poj.org/problem?id=1065
??? Name? : 1065 Wooden Sticks
?
??? Date? : Monday, July 9, 2012
??? Time Stage : one hour
?
??? Result:
10405687??? panyanyany
1065
Accepted??? 248K??? 16MS??? C++
1730B?? 2012-07-09 12:30:02
?
Test Data :
?
Review :
跟 POJ 3636 是差不多的，只不过这里对h,w列都要从小到大排序。然后对其中一列求下降子序列。
//----------------------------------------------------------------------------*/?
?
#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??? 10009?
?
#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;?
}?
?
NODE a[MAXN];?
int order[MAXN];?
?
int LDesS(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)?
??? {?
??????? l = 1;?
??????? r = len;?
??????? while (l <= r)?
??????? {?
??????????? m = (l + r) >> 1;?
??????????? if (order[m] > a[i].h)?
??????????????? l = m + 1;?
??????????? else?
??????????????? r = m - 1;?
??????? }?
?
??????? if (order[l] < a[i].h)?
??????????? order[l] = a[i].h;?
??????? len = max(len, l);?
??? }?
??? return len;?
}?
?
int main()? www.2cto.com
{?
??? int i, tc, n;?
??? while (scanf("%d", &tc) != EOF)?
??? {?
??????? while (tc--)?
??????? {?
??????????? scanf("%d", &n);?
??????????? for (i = 0; i < n; ++i)?
??????????????? scanf("%d %d", &a[i].w, &a[i].h);?
?
??????????? printf("%d\n", LDesS(a, n));?
??????? }?
??? }?
??? return 0;?
}?
?作者：panyanyany