/* THE PROGRAM IS MADE BY PYY */?
/*----------------------------------------------------------------------------//
??? Copyright (c) 2012 panyanyany All rights reserved.
?
??? URL?? : http://poj.org/problem?id=1548
??? Name? : 1548 Robots
?
??? Date? : Monday, July 9, 2012
??? Time Stage : half an hour
?
??? Result:
10405836??? panyanyany
1548
Accepted??? 172K??? 0MS C++
1775B?? 2012-07-09 13:02:39
?
Test Data :
?
Review :
?
//----------------------------------------------------------------------------*/?
?
#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??? (24*25)?
?
#define L(x)??? ((x)<<1)?
#define R(x)??? (((x)<<1)|1)?
#define M(x, y) (((x)+(y)) >> 1)?
?
#define DB??? //?
?
struct NODE {?
??? int x, y;?
};?
?
bool cmp(const NODE &lhs, const NODE &rhs)?
{?
??? if (lhs.x == rhs.x)?
??? return lhs.x < rhs.x;?
}?
?
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].y)?
??????????????? l = m + 1;?
??????????? else?
??????????????? r = m - 1;?
??????? }?
?
??????? if (order[l] < a[i].y)?
??????????? order[l] = a[i].y;?
??????? len = max(len, l);?
??? }?
??? return len;?
}?
?
int main()?
{?
??? int x, y, n;?
??? n = 0;?
??? while (scanf("%d %d", &x, &y) != EOF)?
??? {?
??????? if (x == -1 && y == -1)?
??????????? break;?
?
??????? if (x != 0 && y != 0)?
??????? {?
??????????? a[n].x = x;?
??????????? a[n].y = y;?
??????????? ++n;?
??????? }?? www.2cto.com
??????? else?
??????? {?
??????????? printf("%d\n", LDesS(a, n));?
??????????? n = 0;?
??????? }?
??? }?
??? return 0;?
}?
作者：panyanyany