题解【CJOJ1070/UVA】嵌套矩形

Description

有 n 个矩形，每个矩形可以用两个整数 a, b 描述，表示它的长和宽。矩形 X(a, b) 可以嵌套在矩形 Y(c, d) 中当且仅当 a＜c, b＜d，或者 b＜c, a＜d（相当于把矩形 X 旋转了 90°）。例如 (1, 5) 可以嵌套在 (6, 2) 内，但不能嵌套在 (3, 4) 内。
你的任务是选出尽量多的矩形，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。

Input

第一行一个正整数 n (n <= 1000)。
接下来 n 行每行两个正整数 a, b 表示矩形 i 的长和宽。

Output

第一行一个整数 k 表示符合条件的最多矩形数。
第二行 k 个整数依次表示符合条件矩形的编号，要求字典序最小。

Sample Input

8
14 9
15 19
18 12
9 10
19 17
15 9
2 13
13 10

Sample Output

4
4 8 3 2

Hint

最大嵌套深度为 4 。
4 个矩形分别是：4(9, 10) ＜ 8(13, 10) ＜ 3(18,12) ＜ 2(15,19)

Source

入门经典，DP，DAG(有向无环图)

Solution

此题是最长路模板。

最长路可以用DP来求，具体实现过程是这样的：

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];//返回
}

有了这个模板，此题就非常好做了：

　　先预处理处所有相连接的边，然后进行DP，最后统计答案。

Code

  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
",dp[sum]);//输出总数
115 
116     print(sum);//打印路径
117 
118     return 0;
119 }