题目描述

难度分:$1900$

输入$n(1 \leq n \leq 1000)$，$k(2 \leq k \leq 5)$和$k$个$1$~$n$的排列。

输出这$k$个排列的最长公共子序列$LCS$的长度。

输入样例

4 3
1 4 2 3
4 1 2 3
1 2 4 3

输出样例

3

算法

图论+动态规划

由于要求的是公共子序列，序列的每个元素在所有数组中的相对顺序都应该是一样的。所以对于两个数$i$和$j$而言，如果每个数组都满足$i$在$j$的前面，就从$i$向$j$连一条有向边，接下来就可以在这个$DAG$上做动态规划了。

状态定义

$dp[i]$表示以数字$i$开头的公共子序列最大长度，最终的答案就是$max_{i \in [1,n]}dp[i]$。

状态转移

$cur$可以向它所有的后继节点$nxt$转移，相当于数字$cur$后面接上数字$nxt$可以存在于所有的$k$个数组中，因此状态转移方程为$dp[cur]=1+max_{nxt}dp[nxt]$。

复杂度分析

时间复杂度

建图的时间复杂度是$O(kn^2)$。枚举公共子序列的起点数字$i$时间复杂度为$O(n)$，从数字$i$开始遍历整个图求最长路时间复杂度为$O(n+m)$（$m$表示边的数量，和$n$同一级别，是个稀疏图）。因此，算法整体的时间复杂度为$O(kn^2)$。

空间复杂度

$dp$数组的空间消耗是$O(n)$；$DAG$的邻接表空间消耗是$O(n+m)$（$m$表示边的数量，和$n$同一级别，是个稀疏图）；在建图的过程中，为了确定每个数对之间是否有边，需要一个$n \times n$规模的数组$pos$来记录每个数组中某个数值的索引位置，空间复杂度为$O(n^2)$。因此，整个算法的额外空间复杂度为$O(n^2)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1001;
int n, k, a;
int pos[N][N], dp[N];
vector<int> graph[N];

int dfs(int cur) {
    if(~dp[cur]) return dp[cur];
    int res = 0;
    for(int nxt: graph[cur]) {
        res = max(res, dfs(nxt));
    }
    return dp[cur] = res + 1;
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= k; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &a);
            pos[i][a] = j;
        }
    }
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) continue;
            int cnt = 0;
            for(int idx = 1; idx <= k; idx++) {
                cnt += pos[idx][i] < pos[idx][j]? 1: 0;
            }
            // 每个数组都有j在i的后面
            if(cnt == k) {
                graph[i].push_back(j);
            }
        }
    }
    int ans = 1;
    // 枚举起点
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dfs(i));
    }
    printf("%d\n", ans);
    return 0;
}