Codeforces 463D(DAG 图最长路)

Codeforces 463D
题意：求$k$个序列的最长公共序列长度。

如果是两个序列，则为经典 DP 问题。对于最长与 DP ，可以联想到 DAG 图最长路。
对于每个序列，如果一个数在另一个数前面，并且每个序列都存在这样的关系，就在他们之间连上有向边，显然是一个 DAG 图，然后求一个 DAG 图最长路长度+1即为答案。

本题采用了 DAG 图最长路模型，其核心为 DP 与 最长。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

const int MAXN = 1000 + 5;

int n, k, ma[MAXN][MAXN], tmp[MAXN], ino[MAXN], dp[MAXN], ans = 0;
vector<int> G[MAXN];

int DP(int u) {
    if (dp[u] != 0) return dp[u];
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        dp[u] = max(dp[u], DP(v) + 1);
        ans = max(ans, dp[u]);
    }
    return dp[u];
}

void clean() {
    ms(ino, 0);
}
int solve() {
    clean();
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) scanf("%d", &tmp[j]);
        for (int j = 1; j <= n; j++) 
        for (int k = j + 1; k <= n; k++) ma[tmp[j]][tmp[k]]++;
    }

    for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++) if (ma[i][j] == k) G[i].push_back(j), ino[j]++;

    for (int i = 1; i <= n; i++) dp[i] = 0;
    for (int i = 1; i <= n; i++) if (!ino[i]) DP(i);

    printf("%d\n", ans + 1);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &k), solve();
    return 0;
}