南陽理工学院OJ 16矩形ネスト
1837 ワード
長方形のネスト
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、a入力
1行目は正の数N(0各試験データの最初の行は正の数nであり、この試験データのセットに矩形の個数が含まれていることを示す(n<=1000)
その後のn行は,各行に2つの数a,b(0しゅつりょく
テストデータのセットごとに1つの数を出力し、最大条件を満たす矩形の数を表し、各グループの出力は1行を占めます.
サンプル入力
サンプル出力
考え方:
私の長さは順番に並べてください.
その後、矩形ごとに最大何個カバーできるかを逆さまに求めます.
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、a
1行目は正の数N(0
その後のn行は,各行に2つの数a,b(0
テストデータのセットごとに1つの数を出力し、最大条件を満たす矩形の数を表し、各グループの出力は1行を占めます.
サンプル入力
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
サンプル出力
5考え方:
私の長さは順番に並べてください.
その後、矩形ごとに最大何個カバーできるかを逆さまに求めます.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct haha
{
int x;
int y;
}que[2000];
int dp[1002][1002],n,ll[1002];
int cmp(const void *a,const void *b)
{
if((*(struct haha *)a).x!=(*(struct haha *)b).x)
return (*(struct haha *)b).x-(*(struct haha *)a).x;
return (*(struct haha *)b).y-(*(struct haha *)a).y;
}
int main()
{
int cas,i,j,max,temp;
scanf("%d",&cas);
while(cas--)
{
int x,y;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&x,&y);
if(y>x) {temp=x;x=y;y=temp;}
que[i].x=x;
que[i].y=y;
}
qsort(que,n,sizeof(que[0]),cmp);//
max=0;
memset(ll,0,sizeof(ll));
for(i=n-1;i>=0;i--)//
{
int mid=0;
for(j=i+1;j<n;j++)
if(que[i].x>que[j].x&&que[i].y>que[j].y&&mid<ll[j])
mid=ll[j];
ll[i]=mid+1;
if(max<mid+1) max=mid+1;
}
printf("%d
",max);
}
return 0;
}