nyoj 16 직사각형 내장
2262 단어 OJ
시간 제한:
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
9도 OJ 1116: 가감승제(기초문제)시간 제한: 1초 메모리 제한: 32메가바이트 특수 판제: 아니요 제출: 1466 해결 방법: 902 제목 설명: 입력한 연산자에 따라 입력한 정수에 대해 간단한 정수 연산을 진행한다.연산자는 더하기 +, 빼기 -,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
