本文主要是介绍Codeforces #264 (Div. 2) D. Gargari and Permutations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have foundk permutations. Each of them consists of numbers1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?
You can read about longest common subsequence there: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
The first line contains two integers n andk (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the nextk lines contains integers 1, 2, ..., n in some order — description of the current permutation.
Print the length of the longest common subsequence.
4 3 1 4 2 3 4 1 2 3 1 2 4 3
3
The answer for the first test sample is subsequence [1, 2, 3].
题意：求k个长度为n的最长公共子序列
思路1：保存每个数在各自串的位置，因为结果是第1个串中的某个可能，所以我们枚举第1个串的可能，然后检查如果一个以a[j]为结束的最长公共子序列成立的情况是，对于每个串的a[i]都在a[j]的前面，那么就有dp[j] = max(dp[j], dp[i]+1)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1010;int n, k;
int a[maxn][maxn], b[maxn][maxn], dp[maxn];int check(int x, int y) {for (int i = 2; i <= k; i++)if (b[i][x] > b[i][y])return 0;return 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[i][j]);b[i][a[i][j]] = j;}for (int i = 1; i <= n; i++)dp[i] = 1;int ans = 0;for (int i = 1; i <= n; i++) {for (int j = i+1; j <= n; j++) {if (check(a[1][i], a[1][j]))dp[j] = max(dp[i]+1, dp[j]);}}for (int i = 1; i <= n; i++)ans = max(ans, dp[i]);printf("%d\n", ans);return 0;
}
思路2：如果一个数字i在每个串的位置都在j前面，那么i到j就有一条有向边，那么题目就转换为DAG求最长
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1010;int num[10][maxn], vis[maxn];
int n, k;
vector<int> g[maxn];int check(int x, int y) {for (int i = 0; i < k; i++)if (num[i][x] >= num[i][y])return 0;return 1;
}int dfs(int x) {int ans = 0;if (vis[x])return vis[x];int size = g[x].size();for (int i = 0; i < size; i++)ans = max(ans, dfs(g[x][i]));return vis[x] = ans + 1;
}int main() {scanf("%d%d", &n, &k);memset(vis, 0, sizeof(vis));for (int i = 0; i <= n; i++)g[i].clear();int a;for (int i = 0; i < k; i++)for (int j = 1; j <= n; j++) {scanf("%d", &a);num[i][a] = j;}for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (check(i, j))g[i].push_back(j);int ans = 0;for (int i = 1; i <= n; i++)if (!vis[i])ans = max(ans, dfs(i));printf("%d\n", ans);return 0;
}这篇关于Codeforces #264 (Div. 2) D. Gargari and Permutations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
