本文共 1358 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：

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

题目分析：

• 第一次做这种排列的dp，感觉学到了一种新的定义状态的方法。
• 首先我们要记录pos[i][j]代表第i行数j出现的位置。
• cnt[i]记录当前扫过的范围内数i出现的次数 。
• dp[i]表示以数i结尾的最长公共子序列的长度。
• 我们首先遍历的是序列的长度，然后每次扫描每一行上的数，更新cnt[i],然后如果cnt[i]==k,那么证明利用前j列能够得到以i结尾的公共子序列，那么我们遍历已经更新过的k，满足对于所有的行都满足pos[j]>pos[k]的，就可以更新dp[i] = max ( dp[i] , dp[k]+1 )
• 最后枚举以每一个数结尾的情况，判断最大的情况即可。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAX 1007using namespace std;int n,k;int dp[MAX];int pos[MAX][MAX];int a[MAX][MAX];int cnt[MAX];vector
        
          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\n" , pp ); }}
        
       
      
     
    
   

转载地址：http://uqvjn.baihongyu.com/