CFR 463 D. Gargari and Permutations ( LCS DP )

Problem - D - Codeforces
Problem in short: Given k arrays of 1 ~ n permutation, find max LCS length
Since the final LCS will be in the first array anyways, we can describe the state as
dp[ i ] : maximum length of LCS when a[ 0 ][ i ] is the last element in LCS
then we will have
dp[ i ] = max{ dp[ j ] + 1 }, for all j < i AND pos[ c ][ a[ 0 ][ j ] ] < pos[ c ][ a[ 0 ][ i ] ], for all c < k
which means it is only allowed to take the next number when the two numbers are ordered the same way in all arrays.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
const int MAXK = 5 + 2;

int n, k;
int a[ MAXK ][ MAXN ];
int pos[ MAXK ][ MAXN ];

int dp[ MAXN ];

void solve(){
    for( int c = 1; c < k; ++c )
        for( int i = 0; i <= n; ++i )
            pos[ c ][ a[ c ][ i ] ] = i;
    for( int i = 1; i <= n; ++i ){
        for( int j = 0; j < i; ++j ){
            int x = a[ 0 ][ j ], y = a[ 0 ][ i ];
            bool ok = true;
            for( int c = 1; c < k; ++c )
                if( pos[ c ][ x ] > pos[ c ][ y ] )
                    ok = false;
            if( ok ) dp[ i ] = max( dp[ i ], dp[ j ] + 1 );
        }
    }
    int ans = 0;
    for( int i = 1; i <= n; ++i )
        ans = max( ans, dp[ i ] );
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &k);
    for( int i = 0; i < k; ++i )
        for( int j = 1; j <= n; ++j )
            scanf("%d", &a[ i ][ j ]);
    solve();
    return 0;
}