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

思路：见紫书。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 #include <cstring>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #define FRER() freopen("in.txt", "r", stdin)

 #define FREW() freopen("out.txt", "w", stdout)

 #define INF 0x3f3f3f3f

 using namespace std;

 /*

 1

 10

 1 2

 2 4

 5 8

 6 10

 7 9

 3 1

 5 8

 12 10

 9 7

 2 2

 */

 const int maxn =  + ;

 typedef pair<int, int> P;

 P point[maxn];

 int G[maxn][maxn], d[maxn], n;

 int dp(int i) {

     if(d[i])

         return d[i];

     int& ans = d[i];

     ans = ;

     for(int j = ; j <= n; ++j)

         if(G[i][j])

             ans = max(ans, dp(j) + );

     return ans;

 }

 void print(int i) {

     cout << i << ' ';

     for(int j = ; j <= n; ++j)

         if(G[i][j] && d[i] == d[j] + ) {

             print(j);

             return ;

         }

 }

 int main()

 {

     ios::sync_with_stdio();

     cin.tie();

     int T;

     cin >> T;

     while(T--) {

         memset(G, , sizeof(G));

         memset(d, , sizeof(d));

         cin >> n;

         for(int i = ; i <= n; ++i) {

             cin >> point[i].first >> point[i].second;

             for(int j = ; j < i; ++j) {

                 if(point[i].first < point[j].first && point[i].second < point[j].second)

                     G[i][j] = ;

                 else if(point[j].first < point[i].first && point[j].second < point[i].second)

                     G[j][i] = ;

             }

         }

         int idx = ;

         for(int i = ; i <= n; ++i)

             if(dp(i) > d[idx])

                 idx = i;

         cout << d[idx] << endl;

         print(idx);

         cout << endl;

     }

     return ;

 }