题解【CJOJ1070/UVA】嵌套矩形

inline int DP(int p)
{
    if(dp[p]>0)//特判
    {
        return dp[p];
    }

    dp[p]=1;//初值

    for(register int j=1; j<=n; j++)//枚举所有出边
    {
        if(m[p][j]==1)//如果有边
        {
            dp[p]=max(dp[p],DP(j)+1);//就进行DP
        }
    }

    return dp[p];//返回
}

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 inline int read()//快速读入
  6 {
  7     int f=1,x=0;
  8     char c=getchar();
  9 
 10     while(c<‘0‘ || c>‘9‘)
 11     {
 12         if(c==‘-‘)f=-1;
 13         c=getchar();
 14     }
 15 
 16     while(c>=‘0‘ && c<=‘9‘)
 17     {
 18         x=x*10+c-‘0‘;
 19         c=getchar();
 20     }
 21 
 22     return f*x;
 23 }
 24 
 25 struct Node
 26 {
 27     int x,y;
 28 } a[1005];
 29 int n,dp[1005],m[1005][1005],sum=-1;
 30 
 31 inline int check(Node w,Node q)//预处理处矩形是否嵌套
 32 {
 33     if(w.x<q.x && w.y<q.y)return 1;
 34 
 35     if(w.y<q.x && w.x<q.y)return 1;
 36 
 37     return 0;
 38 }
 39 
 40 inline int DP(int p)//DP主过程
 41 {
 42     if(dp[p]>0)
 43     {
 44         return dp[p];
 45     }
 46 
 47     dp[p]=1;
 48 
 49     for(register int j=1; j<=n; j++)
 50     {
 51         if(m[p][j]==1)
 52         {
 53             dp[p]=max(dp[p],DP(j)+1);
 54         }
 55     }
 56 
 57     return dp[p];
 58 }
 59 
 60 inline void print(int ans)
 61 {
 62     printf("%d ",ans);//输出当前边
 63 
 64     for(register int i=1; i<=n; i++)//枚举所有出边
 65     {
 66         if(m[ans][i]==1 && dp[ans]==dp[i]+1)//如果有边
 67         {
 68             print(i);//递归输出
 69 
 70             break;
 71         }
 72     }
 73 }
 74 
 75 int main()
 76 {
 77     memset(dp,-1,sizeof(dp));
 78     memset(m,-1,sizeof(m));
 79 
 80     n=read();
 81 
 82     for(register int i=1; i<=n; i++)
 83     {
 84         a[i].x=read(),a[i].y=read();
 85     }
 86 
 87     for(register int i=1; i<=n; i++)
 88     {
 89         for(register int j=1; j<=n; j++)
 90         {
 91             if(check(a[i],a[j]))
 92             {
 93                 m[i][j]=1;//连边
 94             }
 95         }
 96     }
 97 
 98     for(register int i=1; i<=n; i++)//计算各边长度
 99     {
100         if(dp[i]==-1)
101         {
102             dp[i]=DP(i);
103         }
104     }
105 
106     for(register int i=1; i<=n; i++)//统计答案
107     {
108         if(dp[i]>dp[sum])
109         {
110             sum=i;
111         }
112     }
113 
114     printf("%d\n",dp[sum]);//输出总数
115 
116     print(sum);//打印路径
117 
118     return 0;
119 }