NYoj-16-矩形嵌套-dp

NYoj-16-矩形嵌套-dp

矩形嵌套

描述

有n個矩形，每個矩形可以用a,b來描述，表示長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中當且僅當a

輸入

第一行是一個正正數N(0 每組測試數據的第一行是一個正正數n，表示該組測試數據中含有矩形的個數(n<=1000)
隨後的n行，每行有兩個數a,b(0 輸出

每組測試數據都輸出一個數，表示最多符合條件的矩形數目，每組輸出占一行

樣例輸入

1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2

樣例輸出

5

#include
#include
#include
#include
using namespace std;
int dp[1100];
struct rectangle
{
	int a,b;
}REC[1100];
bool cmp(rectangle x,rectangle y)//對長進行排序，求寬的最大上升子序列 
{
	if(x.a==y.a)
	   return x.bb)
	   return a;
	else
	   return b;
}
int main()
{
	int T,n,x,y,i,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=0;iREC[j].b && dp[j]>ans) 
				   ans=dp[j];
			}
			dp[i]=ans+1;
			ans=0;
		}
		for(i=0;i<=n;i++)
		{
			if(dp[i]>ans)
			  ans=dp[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}