Codeforces 463D(DAG 图最长路)

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}
------ 本文结束 ------