给你k个长度为n的排列,求这些排列的最长公共子序列的长度
题解:k个都是一个排列,所以,每一个数在自己的的排列中只会出现一次,所以,我们可以记录每一个数在k个排列中的位置,然后就变成了k维偏序问题,a[i] <= a[j]
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; struct node { vector<int> vec; }a[maxn]; int dp[maxn]; bool cmp(node a, node b) { return a.vec[0] < b.vec[0]; } int main() { int n, m, x; cin >> n >> m; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> x; a[x].vec.push_back(j); } } sort (a + 1, a + n + 1, cmp); int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { int flag = 1; for (int k = 0; k < m; k++) { if (a[i].vec[k] < a[j].vec[k]) { flag = 0; } } if (flag) { dp[i] = max(dp[i], dp[j]); } } dp[i]++; ans = max(ans, dp[i]); } cout << ans << endl; return 0; }