Codeforces Round #264 (Div. 2) D. Gargari and Permutations DP

链接：

http://codeforces.com/contest/463/problem/D

题意：

给出k个排列，问这k个排列的最长公共子序列的长度。

题解：

首先cnt记录的是i在j的前面有多少个，因为是k的排列的公共子序列，所以只有当cnt[i][j]==k的时候才会考虑

然后就是求这么多组边能连起来的最长路径，就有点类似dijkstra了

代码：

31 int n, k;
32 int a[MAXN];
33 int cnt[MAXN][MAXN];
34 VI G[MAXN];
35 int dp[MAXN];
36 
37 int main() {
38     ios::sync_with_stdio(false), cin.tie(0);
39     cin >> n >> k;
40     rep(i, 0, k) {
41         rep(j, 0, n) cin >> a[j];
42         rep(p, 0, n) rep(q, p + 1, n) cnt[a[p]][a[q]]++;
43     }
44     rep(i, 1, n + 1) rep(j, 1, n + 1) if (cnt[i][j] == k) G[j].pb(i);
45     queue<int> que;
46     rep(i, 1, n + 1) if (!G[i].empty()) que.push(i);
47     while (!que.empty()) {
48         int u = que.front(); que.pop();
49         rep(i, 0, G[u].size()) {
50             int v = G[u][i];
51             if (dp[v] < dp[u] + 1) {
52                 dp[v] = dp[u] + 1;
53                 que.push(v);
54             }
55         }
56     }
57     int ans = 0;
58     rep(i, 1, n + 1) ans = max(ans, dp[i]);
59     cout << ans + 1 << endl;
60     return 0;
61 }