#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std; struct p {int a,b;}nn[2005]; int cmp(p x,p y) { if(x.a<y.a) return true;//排序 if(x.a==y.a&&x.b<y.b) return true; else return false; } void o(int i,int a,int b) { nn[i].a=a;nn[i].b=b; } int main() { int T; cin>>T; while(T--) { int i,N,x,y,t,j,num[1005],max,k=0; cin>>N; for(i=0;i<N;i++) { scanf("%d %d",&x,&y); o(k++,x,y);o(k++,y,x);//传到到结构体去 } N=2*N; int maxx=0; sort(nn,nn+N,cmp); for(i=0;i<N;i++) num[i]=1; for(i=1;i<N;i++) { int max=0; for(j=i-1;j>=0;j--) if(nn[i].a>nn[j].a&&nn[i].b>nn[j].b&&max<num[j]) max=num[j]; num[i]+=max;每一个能嵌套的最大值存到num[i]数组里,如果能存的话说面就加上这个值。 if(maxx<num[i]) maxx=num[i];//求最大值 } cout<<maxx<<endl; } return 0; }