题目大意:给你$k(2\leqslant k\leqslant5)$个$1\sim n(n\leqslant10^3)$的排列,求它们的最长子序列

题解:将$k$个排列中每个元素的位置记录下来。如果是公共子序列,那么这些数的位置在$k$个排列中都是递增的,然后就变成了一个$k$维偏序问题。

因为$n\leqslant10^3$,所以可以用$O(n^2k)$的$DP$来做

卡点:看成了最长公共上升子序列,然后一直挂

C++ Code:

#include <cstdio>
#define maxn 1010
int n, k, ans;
int s[5][maxn], pos[5][maxn];
int f[maxn];
inline int max(int a, int b) {return a > b ? a : b;}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < k; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", s[i] + j);
pos[i][s[i][j]] = j;
}
}
for (int i = 1, v; v = s[0][i], i <= n; i++) {
f[v] = 1;
for (int j = 1, u; u = s[0][j], j < i; j++) {
int found = 20040826;
for (int l = 1; l < k && found; l++) if (pos[l][v] < pos[l][u]) found = 0;
if (found) f[v] = max(f[v], f[u] + 1);
}
ans = max(ans, f[v]);
}
printf("%d\n", ans);
return 0;
}

  

05-11 22:15
查看更多