算法题：嵌套矩形

问题描述

有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行n (n≤2000)
第2到n+1行每行两个数a,b，表示这个矩形的长和宽

输出格式

一个数，最多符合条件的矩形数目

样例

输入

3 
1 5 
6 2 
3 4

输出

2

解决方案

思路

有向无环图&动态规划

A嵌套在B中就把A和B添加一条边，就变成了搜索最长路径的问题了。
需要使用记忆化搜索，否则会超时。

代码

#include <iostream>
#include <vector>

using namespace std;

struct Obj {
    int a, b;
};

const int N = 2005;

Obj arr[N];         //矩形
vector<int> g[N];   //图
int dp[N];


int dfs(int x) {
    if (dp[x])
        return dp[x];

    int res = 1;
    for (int i = 0; i < g[x].size(); ++i) {
        res = max(res, dfs(g[x][i]) + 1);
    }
    return dp[x] = res;
}

int main() {

    int n;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i].a >> arr[i].b;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((arr[i].a > arr[j].a && arr[i].b > arr[j].b) || (arr[i].b > arr[j].a && arr[i].a > arr[j].b)) {
                g[i].push_back(j);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dfs(i));
    }

    cout << ans;

    return 0;
}