2019-03-16 矩阵嵌套

时间限制: 1Sec 内存限制: 128MB 提交: 109 解决: 14

题目描述
有 n 个矩形，每个矩形可以用 a,b来描述，表示长和宽。矩形 X(a,b)可以嵌套在矩形 Y(c,d)中当且仅当 a <c,b<d或者 b<c,a<d

（相当于旋转 90 度）。例如（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
提示
无
来源
无

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1000+10; 
int N,n;
typedef struct node{
    int a,b;
}Node;
Node A[maxn];
bool ok[maxn][maxn];
int res[maxn]; 
int vis[maxn];
int DFS(int u)
{
    if(res[u]!=0) return res[u];
    for(int i=1;i<=n;i++)
    {
        if(!vis[i] && ok[i][u])
        {
            vis[i]=true;
            res[u]=max(res[u],DFS(i));
            vis[i]=false;
        }
    }
    res[u]++;
    return res[u];
}
bool match(int idx1,int idx2)
{
    if(idx1==idx2) return false;
    if(A[idx1].a<A[idx2].a && A[idx1].b<A[idx2].b) return true;
    if(A[idx1].a<A[idx2].b && A[idx1].b<A[idx2].a) return true;
    return false;
}
int main(void)
{
    int a,b;
    cin>>N;
    while(N--)
    {
        fill(res,res+maxn,0);
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a>>b;
            A[i].a=a,A[i].b=b;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(match(i,j)) ok[i][j]=true;
                else ok[i][j]=false;
            }
        }
        int m=-1;
        for(int i=1;i<=n;i++) 
        {
            vis[i]=true;
            m=max(m,DFS(i));
            vis[i]=false;
        }
        cout<<m;
        if(N!=0) cout<<endl;
    }
    return 0;
}