南阳理工OJ 16 矩形嵌套

/*
做了一天题，现在已经昏昏沉沉了·····

先按矩形面积把小矩形从小到大排序，然后用动态规划做。
p[i]=max(p[1],p[2],p[3].....).
p[i]为前i个矩形中可以嵌套的最多的矩形。
具体实现看代码！
*/
#include<stdio.h>
#include<algorithm>
struct JX
{
	int a;
	int b;
	int date;//date里面存放这个矩形可以嵌套的最多的个数
}jx[1010];
bool neng(JX x,JX y)//判断x能否嵌套y（注意没有等于号！）
{
	return(x.a>y.a&&x.b>y.b||x.a>y.b&&x.b>y.a);
}
bool cmp(JX x,JX y)//快排重载函数（按面积排序）
{
	return(x.a*x.b<y.a*y.b);
}
int main()
{
//	freopen("in.txt","r",stdin);  //把in.txt中‘.’错写成‘,’就让我调试好大一会~~不明白为什么会出现那么奇怪的结果
	int T, n,i,j,max,m;
	scanf("%d",&T);
	while(T--)
	{
		m=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)//输入数据
		{
			scanf("%d%d",&jx[i].a,&jx[i].b);
			jx[i].date=1;
		}
		std::sort(jx,jx+n,cmp);//排序
		for(i=0;i<n;i++)
		{
			max=0;
			for(j=0;j<i;j++)//找出第i个以前可以嵌套的最大的数
				if(neng(jx[i],jx[j])&&max<jx[j].date)//J能嵌套在I里
					max=jx[j].date;
			jx[i].date+=max;//找到以后加到i上
			if(m<jx[i].date)m=jx[i].date;//找出最大的结果
		}
		printf("%d\n",m);//输出
	}
	return(0);
}