CodeForces 463D DP

Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?

You can read about longest common subsequence there: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Input

The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.

Output

Print the length of the longest common subsequence.

Examples

Input

Output

Note

The answer for the first test sample is subsequence [1, 2, 3].

OJ-ID：
CodeForce 113B

author：
Caution_X

date of submission：
2019-09-27

tags：
DP

description modelling：
求多个数列的LCS

major steps to solve it：
1.dp[i]:表示以数字i结尾得到的LCS，pos[i][j]表示数字j再第i个数列的位置，cnt[i]表示数字i出现了几次
2.从每个数列第一个数开始往后遍历，当cnt[i]=k时说明i可以作为LCS的一部分了
3.接下来需要讨论一下，在LCS中加入i对答案的影响
4.我们用vector<>存入所有可以作为LCS一部分的值，然后遍历vector中的数，判断二者的pos，来决定i应该插入在哪一个位置
5.遍历完成后vector<>加入i并且重新从2步骤开始

warnings：

AC code:

#include<bits/stdc++.h>

using namespace std;

int a[][];

int dp[];//以i结尾的LCS

int cnt[],pos[][];//pos[i][j]=：j在 i中出现的位置

vector<int> q;

int main()

{

    //freopen("input.txt","r",stdin);

    int n,k,ans=;

    scanf("%d%d",&n,&k);

    for(int i=;i<k;i++)

        for(int j=;j<n;j++)

            scanf("%d",&a[i][j]);

    memset(cnt,,sizeof(cnt));

    memset(dp,,sizeof(dp));

    for(int i=;i<n;i++){

        for(int j=;j<k;j++){

            int cur=a[j][i];

            pos[j][cur]=i;

            cnt[cur]++;

            if(cnt[cur]==k){

                if(q.empty())    dp[cur]=;

                else{

                    for(int kk=;kk<q.size();kk++){

                        bool flag=false;

                        for(int l=;l<k;l++){

                            if(pos[l][q[kk]]>pos[l][cur]){

                                flag=true;

                                break;

                            }

                        }

                        if(!flag)    dp[cur]=max(dp[cur],dp[q[kk]]+);

                        else    dp[cur]=max(dp[cur],);

                    }

                }

                ans=max(ans,dp[cur]);

                q.push_back(cur);

            }

        }

    }

    printf("%d\n",ans);

    return ;

}

巴特西

CodeForces 463D DP

最新文章

热门文章