NYOJ 矩形嵌套--16

一模一样的

#include<stdio.h>
#include<stdlib.h>

struct Node
{
    int a;
    int b;
} s[1001];
int max(int a,int b)
{
	if(a>b) return a;
	else return b;
}
int cmp(const void *a,const void *b)
{
    struct Node *c=(Node *)a;
    struct Node *d=(Node *)b;
    if(c->a!=d->a) return c->a-d->a;
    else return c->b-d->b;
}
int main()
{
    int N;
    scanf("%d",&N);
    while(N--)
    {
        int dp[1001];
        int i,j;
        int n;
        int x,y;
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%d %d",&x,&y);
            if(x>y)
            {
                s[i].a=x;
                s[i].b=y;
            }
            else
            {
                s[i].a=y;
                s[i].b=x;
            }
        }
        qsort(s,n,sizeof(s[0]),cmp);
        for(i=0;i<n;i++)
        {
            dp[i]=1;
            for(j=0;j<i;j++)
            {
                if((s[j].b<s[i].b&&s[j].a<s[i].a)) 
                    dp[i]=max(dp[i],dp[j]+1);
            }
        }
        int max=0;
        for(i=0; i<n; i++)
        {
        	 if(max<dp[i]) max=dp[i];
		}  
        printf("%d\n",max);
    }
    return 0;
}