矩阵嵌套 （线性dp）

解题思路:

改题目有两个方法，写了简单的那种，还有一种是模仿最长上升子序列的，

注意事项:

注意重置数据就好了

参考代码:

#pragma comment(linker, "/STACK:1024000000, 1024000000")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

struct Rec {

    int a,b;

}rec[1010];

int tao[1010][1010];

int dp[1010];

int d(int cur) {

    if(dp[cur]) return dp[cur];

    dp[cur] = 1;

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

        if(tao[cur][i]) {

            dp[cur] = max(dp[cur],d(i)+1);

        }

    }

    return dp[cur];

}

int main()

{

   // freopen("in.txt","r",stdin);

    int t;

    scanf("%d",&t);

    for(int c = 0; c < t; c++) {

        memset(tao,0,sizeof(tao));

        memset(dp,0,sizeof(dp));

        scanf("%d",&n);

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

            scanf("%d%d",&rec[i].a,&rec[i].b);

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

                if(rec[i].a < rec[j].a && rec[i].b < rec[j].b || rec[i].a < rec[j].b && rec[i].b < rec[j].a)

                    tao[j][i] = 1;

                else if(rec[i].a > rec[j].a && rec[i].b > rec[j].b || rec[i].a > rec[j].b && rec[i].b > rec[j].a)

                    tao[i][j] = 1;

            }

        }

        int maxn = -1;

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

            if(!dp[i]) maxn = max(maxn,d(i));

        }

        printf("%d\n",maxn);

    }

    return 0;

}