NYOJ_16_長方形のネスト
4911 ワード
少し小さな穴の厳格な単調な増加シーケンスは、主にそこに穴を並べた.
考え方:矩形のネスト? (a
考え方:矩形のネスト? (a
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
struct point
{
int x,y;
}p[1005];
bool cmp(point a,point b)
{
if(a.x==b.x) // y
return a.y>b.y;
return a.x<b.x;
}
int main()
{
int t,n,i,j,k,a,b,re[1005][2]; //re[i][j] i
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;++i)
{
scanf("%d%d",&a,&b);
if(a>b) swap(a,b); // a<b
p[i].x=a;
p[i].y=b;
}
sort(p,p+n,cmp);
int count=0; //
re[0][0]=0,re[0][1]=0;
for(i=0;i<n;++i)
for(j=count;j>=0;--j)
{
if(p[i].x>re[j][0]&&p[i].y>re[j][1]) // ？
{
re[j+1][0]=p[i].x;
re[j+1][1]=p[i].y;
if(j+1==count+1)
count++;
break;
}
}
printf("%d
",count);
}
return 0;
}