CF 463D (DP 或者 偏序)

给你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;
}