CF463D Gargari and Permutations dp

给定 $n<=10$ 个 $1$~$n$ 的排列，求这些排列的 $LCS$.

考虑两个排列怎么做：以第一个序列为基准，将第二个序列的元素按照该元素在第一个序列中出现位置重新编号.

然后，求一个 $LIS$ 即可.

现在是多个串，不妨也按照这个方法来做：

以第一个串为基准，其余串重新编号成该元素在第一个串中的出现位置.

那么，如果一个序列是 $n$ 个序列的 $LCS$，则满足两个条件：

1: 是重现编号后的 $LCS$

2: 这个 $LCS$ 还需是一个 $LIS$.

多了第二个限制，问题就简单了：令 $f[i]$ 表示这些新编号串以 $i$ 数字结尾的满足两个条件的最长长度.

转移什么的就简单了~

code:

#include <bits/stdc++.h>

#define N 1004

using namespace std;

void setIO(string s)

{

    string in=s+".in";

    string out=s+".out";

    freopen(in.c_str(),"r",stdin);

    freopen(out.c_str(),"w",stdout);

}

struct node

{

    int l,r;

}t[N];

int a[12][N],pos[N],f[N],L[12][N];

int main()

{

    // setIO("seq");

    int n,i,j,m,ans=1;

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

    for(i=1;i<=m;++i)   for(j=1;j<=n;++j)   scanf("%d",&a[i][j]);

    for(i=1;i<=n;++i)   pos[a[1][i]]=i;

    for(i=1;i<=m;++i)   for(j=1;j<=n;++j)   a[i][j]=pos[a[i][j]];

    for(i=1;i<=m;++i)   for(j=1;j<=n;++j)   L[i][a[i][j]]=j;

    f[1]=1;

    for(i=2;i<=n;++i)

    {

        f[i]=1;

        for(j=1;j<i;++j)

        {

            int flag=0;

            for(int k=1;k<=10;++k)    if(L[k][j]>L[k][i])   flag=1;

            if(!flag)    f[i]=max(f[i], f[j]+1),  ans=max(ans, f[i]);

        }

    }

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

    return 0;

}

巴特西

CF463D Gargari and Permutations dp

最新文章

热门文章