nyoj 16 矩形嵌套

时间:2022-09-08 11:12:33
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct p
{int a,b;}nn[2005];
int cmp(p x,p y)
{
    if(x.a<y.a) return true;//排序
    if(x.a==y.a&&x.b<y.b) return true; 
    else return false;
}
void o(int i,int a,int b)
{
    nn[i].a=a;nn[i].b=b;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int i,N,x,y,t,j,num[1005],max,k=0;
        cin>>N;
        for(i=0;i<N;i++)
          {
              scanf("%d %d",&x,&y);
              o(k++,x,y);o(k++,y,x);//传到到结构体去
          }
          N=2*N;
          int maxx=0;
          sort(nn,nn+N,cmp);
          for(i=0;i<N;i++)  num[i]=1;
          for(i=1;i<N;i++)
              {
                  int max=0;
                for(j=i-1;j>=0;j--)
                   if(nn[i].a>nn[j].a&&nn[i].b>nn[j].b&&max<num[j])
                      max=num[j];
                      num[i]+=max;每一个能嵌套的最大值存到num[i]数组里,如果能存的话说面就加上这个值。
                      if(maxx<num[i]) maxx=num[i];//求最大值
              }
              cout<<maxx<<endl;
    }
   return 0;
}