http://acm.pku.edu.cn/JudgeOnline/problem?id=3636貪心+二分。先按w升序，w相同按h降序排。
5
1 8 2 4 2 3 3 5 4 4
答案應(yīng)該為3。
二分就是新建一個(gè)數(shù)組保存每個(gè)嵌套dolls的w和h，并及時(shí)增加或更新到最大。
#include<iostream>
#include<algorithm>
using namespace std;
struct Node
{
int l,w;
bool operator<(const Node &a) const
{
if(l==a.l)
return w>a.w;
return l<a.l;
}
}node[20001],pos[20001];
int main()
{
int n,i,t,num;
scanf("%d",&t);
while(t--&&scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%d%d",&node[i].l,&node[i].w);
sort(node,node+n);
num=0;
int right,left,mid;
for(i=0;i<n;i++)
{
left=0,right=num;
while(left<right)
{
mid=(left+right)/2;
if(pos[mid].l>=node[i].l||pos[mid].w>=node[i].w)
left=mid+1;
else
right=mid;
}
if(num==left)
num++;
pos[left].l=node[i].l;
pos[left].w=node[i].w;
}
printf("%d\n",num);
}
return 0;
}