这个问题据说是dp问题，不过我觉得只用到了一点
dp知识，先把矩形排序，宽对应宽长对应长；然后
对宽或者长进行排序（二级排序），再找出另一方的最大上升子
序列，即可。
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h># define maxn 1000int cmp(const void *a,const void *b){ int* c = (int *)a; int* d = (int *)b;if(*c != *d)return *c - *d;return *(d+1) - *(c+1);}int main(){int a[maxn+10][5];int b[maxn+10];int t,n,i,j,temp;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&a[i][0],&a[i][1]);if(a[i][0] > a[i][1]){temp = a[i][0];a[i][0] = a[i][1];a[i][1] =temp;}}qsort(a,n,sizeof(a[0]),cmp);int max=0;for(i=0;i<n;i++){max = 0;for(j=i-1;j>=0;j--){if(a[j][1]<a[i][1] && b[j]>max)max = b[j];}b[i] = max + 1;}int count = 0;for(i=0;i<n;i++)if(b[i] > count)count = b[i];printf("%d\n",count);}return 0;}
