T1408 矩阵嵌套（DAG 记忆化搜索）

T1408 矩阵嵌套

​ 有 n 个矩阵，每个矩阵有长 x 和宽 y 。我们定义矩阵 A 可以嵌套在矩阵B 中：A.x > B.x 且 A.y > B.y 或者 A.x > B.y 且 A.y > B.x。我们现在要找一个最长的序列，使得序列中除了最后一个矩阵的每一个矩阵都可以被下一个矩阵嵌套。输出这个最长的序列的长度。

思路：

​ 我们要对这个题目进行建图，这一点是比较难想到的。那这个图是怎么建起来的呢？就是根据题目给出的嵌套的定义。假设矩阵 A 可以被 B 嵌套，那我们就可以给 A 到 B 连上一条边，这样一张DAG（有向无环图）就建起来了。建完图之后，在DAG上做一个最长路的记忆化搜索就可以了。

代码：

#include <bits/stdc++.h>

using namespace std;
const int N = 1005;
int n;
int g[N][N];
int f[N]; //表示以i为起点的最长路

int dfs(int u) //DAG上记忆化搜索
{
    if(f[u] != -1)
        return f[u];
    f[u] = 1;
    for(int i = 0; i < n; i ++)
    {
        if(g[u][i] == 1)
            f[u] = max(f[u], dfs(i) + 1); //从自己连向的边中选一条最长的
    }
    return f[u];
}

void init() //初始化
{
    for(int i = 0; i < n; i ++)
        f[i] = -1;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            g[i][j] = 0;
}

void solve()
{
    cin >> n;
    init();
    vector<pair<int, int> > vc(n);
    for(int i = 0; i < n; i ++)
        cin >> vc[i].first >> vc[i].second;
    
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(i == j)  continue;
            int a = vc[i].first, b = vc[i].second;
            int c = vc[j].first, d = vc[j].second;
            if((a < c && b < d) || (a < d && b < c))
                g[i][j] = 1; //从i到j连一条边
        }
    }
    
    int res = 0;
    for(int i = 0; i < n; i ++)
        f[i] = dfs(i), res = max(res, f[i]);
    cout << res << '\n';
}

int main()
{
    int _;
    cin >> _;
    while(_--)
        solve();
}