nyoj 16 직사각형 내장

직사각형 소켓
시간 제한:
3000 ms  |  메모리 제한: 65535 KB
난이도:
4
 
묘사 하 다.
n 개의 사각형 이 있 습 니 다. 각 사각형 은 a, b 로 설명 할 수 있 습 니 다. 길이 와 폭 을 표시 합 니 다.직사각형 X (a, b) 는 직사각형 Y (c, d) 에 끼 워 넣 을 수 있 으 며 a < c, b < d 또는 b < c, a < d (회전 X90 도 에 해당 함).예 를 들 어 (1, 5) 는 (6, 2) 안에 끼 워 넣 을 수 있 지만 (3, 4) 에 끼 워 넣 을 수 없다.당신 의 임 무 는 가능 한 한 많은 사각형 을 한 줄 로 배열 하여 마지막 을 제외 하고 모든 사각형 을 다음 사각형 에 끼 워 넣 는 것 입 니 다.
 
입력
첫 번 째 줄 은 정수 N (0 < N < 10) 으로 테스트 데이터 그룹 수 를 표시 합 니 다.
각 그룹의 테스트 데이터 의 첫 줄 은 정수 n 으로 이 그룹의 테스트 데이터 에 사각형 의 개수 (n < = 1000) 가 포함 되 어 있 음 을 나타 낸다.
다음 n 줄 은 줄 마다 두 개의 수 a, b (0 < a, b < 100) 가 있 는데 사각형 의 길이 와 폭 을 나타 낸다.
출력
각 조 의 테스트 데 이 터 는 하나의 수 를 출력 하고 가장 많은 조건 에 부합 되 는 사각형 수 를 나타 내 며 각 조 의 출력 은 한 줄 을 차지한다.
샘플 입력

1

10

1 2

2 4

5 8

6 10

7 9

3 1

5 8

12 10

9 7

2 2

샘플 출력

5

      ，              ，       i                i-1            
i   1 i-1         ，                                               ；

i   1 i-1 j    ， 

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

struct record

{

	int x;

	int y;

}s[1100];

bool cmp(record c,record d)

{

	if(c.x!=d.x)

	return c.x<d.x;

	else                       //  x       x   y      

	return c.y<d.y;

}

int main()

{

	int n,m,j,i,l,sum,t,max,mid;

	int dp[1100];

	scanf("%d",&n);

	while(n--)

	{

		sum=0;max=0;

		scanf("%d",&m);		

		for(i=0;i<m;i++)

		{

			t=0;

		    scanf("%d %d",&s[i].x,&s[i].y);

		    if(s[i].x>s[i].y)

		    {

		    	t=s[i].x;

		    	s[i].x=s[i].y;     //           

		    	s[i].y=t;

		    }

		}

		sort(s,s+m,cmp);

		for(i=0;i<=m;i++)

		    dp[i]=1;					 //        i      	

		for(i=1;i<=m;i++)

		{

			for(j=i-1;j>=0;j--)

			{			

			    if((s[i].x>s[j].x)&&(s[i].y>s[j].y))

			    {

			        if(dp[i]<dp[j]+1)

			            dp[i]=dp[j]+1;		            

			    }

			}

		}

			for(i=0;i<m;i++)

			{

				if(sum<dp[i])

				    sum=dp[i];

			}					

		printf("%d
",sum);			

	}

	return 0;

}