zoj 2882
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2882
#define SIZE 20001#include<iostream>#include<algorithm>using namespace std;struct Dolls{ int w; int h;};int cmp(struct Dolls x, struct Dolls y){ if(x.w == y.w) return x.h <= y.h; else return x.w <= y.w;}int main(){ int T; cin >> T; while(T--) { int n, x, y; cin >> n; Dolls st[SIZE]; for(int i = 0; i != n; ++i) { cin >> x >> y; st[i].w = x; st[i].h = y; } sort(st, st + n, cmp); /* LIS*/ int len = 1; int b[SIZE + 1]; b[1] = st[0].h; for(int i = 1; i != n; ++i) { if(st[i].h < b[len]) b[++len] = st[i].h; else { int left = 1, right = len; while(left < right - 1) { int mid = (left + right) / 2; if(st[i].h < b[mid]) right = mid; else left = mid; } if(b[left] > st[i].h) b[left] = st[i].h; else b[right] = st[i].h; } } cout << len << endl; } return 0;}