codeforces 463D Gargari and Permutations(dp)

题目

参考网上的代码的、、、

//要找到所有序列中的最长的公共子序列，
//定义状态dp[i]为在第一个序列中前i个数字中的最长公共子序列的长度，
//状态转移方程为dp[i]=max(dp[i],dp[j]+1); j<i

//先预处理出两个数在所有序列中的位置关系，
//例如两个数a和b，只要在任意一个序列中a在b的后面，则记after[a][b]=1。

//在递推的时候如果!after[a][b]，则进行状态转移。


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

int a[6][1010];
int after[1010][1010];
int dp[1010];
int main () {
    int n,k;
    scanf("%d%d",&n,&k);
    int ii=0;
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    memset(after,0,sizeof(after));
    memset(dp,0,sizeof(dp));
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                after[a[i][k]][a[i][j]]=1; //存在 k在j后面 
            }
        }
    }

    int ans=0;
    
    //直接对1~n进行状态转移不可以
    //要根据第一行来dp
    for(int i=0;i<n;i++)
    {
        dp[i]=1;
        for(int j=0;j<i;j++)
        {
            if(after[a[0][j]][a[0][i]]==0)dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(dp[i],ans);
    }
    printf("%d
",ans);
    return 0 ;
}