#include<stdio.h>
#include<stdlib.h>
struct Node{
	int w;
	int h;
}node[20005];
int B[20005];
int cmp(const void *a,const void *b)
{
	Node *p,*q;
	p=(Node *)a;
	q=(Node *)b;
	if(p->h>q->h)
		return 1;
	else if(p->h==q->h)
		if(p->w<q->w)
			return 1;
	 return -1;
}
int LIS(int m)
{
	int i,mid,left,right,len=1,j;
	B[1]=node[1].w;
	for(i=2;i<=m;i++)
	{
		left=1;right=len;
		while(left<=right)
		{
			mid=(left+right)/2;
			if(B[mid]<=node[i].w)
				right=mid-1;
			else left=mid+1;
		}
			B[left]=node[i].w;
			if(left>len) len++;
	}
	return len;
}
int main()
{
	int ncase;
	int m,i;
	scanf("%d",&ncase);
	while(ncase--)
	{
		scanf("%d",&m);
		for(i=1;i<=m;i++)
			scanf("%d%d",&node[i].h,&node[i].w);
		qsort(node+1,m,sizeof(node[0]),cmp);
		printf("%d\n",LIS(m));
	}
	return 0;
}

• Re:为什么我用的Dilworth定理会超时 (958) soligho 2009-11-19 19:35:05