NYOJ_16_矩形嵌套

有点小坑的严格单调递增序列，主要是排序那里坑了一下。

思路：矩形的嵌套？   (a<c&&b<d)||(a<d&&b<c)?  不，只要在建点时保证a<b，条件就会少一个，直接a<c&&b<d就行了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
struct point
{int x,y;
}p[1005]; 
bool cmp(point a,point b)
{if(a.x==b.x) //保证最后更新的y一定是最小的return a.y>b.y;return a.x<b.x;
}
int main()
{int t,n,i,j,k,a,b,re[1005][2]; //re[i][j]记录i长度的最小符合点scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;++i){scanf("%d%d",&a,&b);if(a>b) swap(a,b); //保证a<bp[i].x=a;p[i].y=b;}sort(p,p+n,cmp);int count=0; //记录长度re[0][0]=0,re[0][1]=0;for(i=0;i<n;++i)for(j=count;j>=0;--j){if(p[i].x>re[j][0]&&p[i].y>re[j][1]) //满足嵌套条件？
             {re[j+1][0]=p[i].x;re[j+1][1]=p[i].y;if(j+1==count+1)count++;break;}}printf("%d\n",count);}return 0;
}