DAG上的动态规划——嵌套矩阵问题

问题描述：有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)内。你的任务是选出尽可能多的矩形排成一行。使得除了最后一个之外，每个矩形都可以嵌套在下一个矩形内。如果有多解，矩阵编号的字典序应该尽量小。

思路：见紫书。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <string>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <queue>
11 #include <deque>
12 #include <stack>
13 #include <list>
14 
15 #define FRER() freopen("in.txt", "r", stdin)
16 #define FREW() freopen("out.txt", "w", stdout)
17 
18 #define INF 0x3f3f3f3f
19 
20 using namespace std;
21 
22 /*
23 1
24 10
25 1 2
26 2 4
27 5 8
28 6 10
29 7 9
30 3 1
31 5 8
32 12 10
33 9 7
34 2 2
35 */
36 const int maxn = 100 + 5;
37 
38 typedef pair<int, int> P;
39 
40 P point[maxn];
41 
42 int G[maxn][maxn], d[maxn], n;
43 
44 int dp(int i) {
45     if(d[i])
46         return d[i];
47     int& ans = d[i];
48     ans = 1;
49     for(int j = 1; j <= n; ++j) 
50         if(G[i][j]) 
51             ans = max(ans, dp(j) + 1);
52     return ans;
53 }
54 
55 void print(int i) {
56     cout << i << ' ';
57     for(int j = 1; j <= n; ++j)
58         if(G[i][j] && d[i] == d[j] + 1) {
59             print(j);
60             return ;
61         }
62 }
63 
64 int main()
65 {
66     ios::sync_with_stdio(0);
67     cin.tie(0);
68 
69     int T;
70     cin >> T;
71     while(T--) {
72         memset(G, 0, sizeof(G));
73         memset(d, 0, sizeof(d));
74         cin >> n;
75         for(int i = 1; i <= n; ++i) {
76             cin >> point[i].first >> point[i].second;
77             for(int j = 1; j < i; ++j) {
78                 if(point[i].first < point[j].first && point[i].second < point[j].second)
79                     G[i][j] = 1;
80                 else if(point[j].first < point[i].first && point[j].second < point[i].second) 
81                     G[j][i] = 1;
82             }
83         }
84         int idx = 0;
85         for(int i = 1; i <= n; ++i) 
86             if(dp(i) > d[idx])
87                 idx = i;
88         cout << d[idx] << endl;
89         print(idx);
90         cout << endl;
91     }
92     return 0;
93 }