NYOJ 16 矩形嵌套(DAG上的动态规划)

【题目链接】NYOJ16-矩形嵌套

【题意】有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

【样例】

样例输入 1 10 1 2 2 4 5 8 6 10 7 9 3 1 5 8 12 10 9 7 2 2 样例输出 5

【分析】

       矩形之间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩形X可以嵌套在矩形Y里，就从X到Y连一条有向边。这个有向图是无环的，因为一个矩形无法直接或间接地嵌套在自己内部。换句话说，它是一个DAG。这样，所要求的便是DAG上 的最长路径。

【代码】

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1005
struct node{
    int x,y,m;
};
node s[maxn];
bool c[maxn][maxn];
int dp[maxn];
bool cmp(node a,node b){
    return a.m<b.m;
}
int main(){
    int T,n;
    cin>>T;
    while(T--){
        scanf("%d",&n);
        memset(c,false,sizeof(c));
        int x,y;
        for(int i=0;i<n;i++){
            scanf("%d%d",&x,&y);
            s[i].x=min(x,y);
            s[i].y=max(x,y);
            s[i].m=x*y;
        }
        sort(s,s+n,cmp);
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s[i].x<s[j].x&&s[i].y<s[j].y){
                    c[i][j]=true;
                }
            }
        }
        int ans=0;
        for(int i=n-1;i>=0;i--){
            dp[i]=1;
            for(int j=i+1;j<n;j++){
                if(c[i][j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}