poj 3636 Nested Dolls 动态更新表的二分查找

题意：

给n个玩具，每个有属性w,h。如果w1<w2且h1<h2那么玩具1可放在玩具2里，问最后最少能有几个玩具。

分析：

w升序，w相同时h降序排序后是可以贪心的，这里使用了动态维护表的二分算法，表里动态维护了每堆玩具中h的最大值（所以w相同时h要降序）。这题我一开始一看是个拓扑图还想着用什么图算法。。没想到直接可以贪心，不可以有思维定式啊~~

代码：

//poj 3636
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN=20012;
struct P{int x,y;
}p[maxN];
int H[maxN];
int cmp(P a,P b)
{return a.x==b.x?a.y>b.y:a.x<b.x;
}
int main()
{int t;scanf("%d",&t);while(t--){int i,n,sum=0;scanf("%d",&n);for(i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y);sort(p,p+n,cmp);int len=0;for(i=0;i<n;++i){int cur=p[i].y;int left=0;int right=len;while(left<right){int mid=(left+right)/2;if(H[mid]>=cur)left=mid+1;elseright=mid;}if(len==left)++len;H[left]=cur;}printf("%d\n",len);}return 0;	
}