codeforces 463D D. Gargari and Permutations(dp)

제목 링크:

제목 대의:

제목 분석:

AC 코드:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 1007

using namespace std;

int n,k;
int dp[MAX];
int pos[MAX][MAX];
int a[MAX][MAX];
int cnt[MAX];
vector<int> ans;

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &k ) )
    {
        ans.clear();
        for ( int i = 1 ; i <= k ; i++ )
            for ( int j = 1 ; j <= n ; j++ )
                scanf ( "%d" , &a[i][j] );
        for ( int i = 1 ; i <= k ; i++ )
            for ( int j = 1 ; j <= n ; j++ )
                pos[i][a[i][j]] = j;
        memset ( dp , 0 , sizeof ( dp ) );
        memset ( cnt , 0 , sizeof ( cnt ) );
        ans.push_back ( 0 );
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = 1 ; j <= k ; j++ )
            {
                int x = a[j][i];
                cnt[x]++;
                if ( cnt[x] == k )
                {
                    for ( int t = 0 ; t < ans.size() ; t++ )
                    {
                        int u = ans[t];
                        bool flag = true;
                        for ( int v = 1 ; v <= k ; v++ )
                            if ( pos[v][u] >= pos[v][x] ) 
                                flag = false;
                        if ( flag )
                            dp[x] = max ( dp[x] , dp[u]+1 );
                    }
                    ans.push_back ( x );  
                    cnt[x]++;
                }
            }
        int pp = 0;
        for ( int i = 1 ; i <= n ; i++ )
            pp = max ( pp , dp[i] );
        printf ( "%d
" , pp );
    }
}