LCS

Accepts: 127

Submissions: 397

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

你有两个序列\{a_1,a_2,...,a_n\}{a1,a2,...,an}和\{b_1,b_2,...,b_n\}{b1,b2,...,bn}. 他们都是11到nn的一个排列. 你需要找到另一个排列\{p_1,p_2,...,p_n\}{p1,p2,...,pn}, 使得序列\{a_{p_1},a_{p_2},...,a_{p_n}\}{ap1,ap2,...,apn}和\{b_{p_1},b_{p_2},...,b_{p_n}\}{bp1,bp2,...,bpn}的最长公共子序列的长度最大.

输入描述

输入有多组数据, 第一行有一个整数TT表示测试数据的组数. 对于每组数据:

第一行包含一个整数n (1 \le n \le 10^5)n(1≤n≤105), 表示排列的长度. 第2行包含nn个整数a_1,a_2,...,a_na1,a2,...,an. 第3行包含nn个整数 b_1,b_2,...,b_nb1,b2,...,bn.

数据中所有nn的和不超过2 \times 10^62×106.

输出描述

对于每组数据, 输出LCS的长度.

输入样例

2

3

1 2 3

3 2 1

6

1 5 3 2 6 4

3 6 2 4 5 1

输出样例

2

4

题目中给出的是两个排列, 于是我们可以先把排列分成若干个环, 显然环与环之间是独立的. 事实上对于一个长度为l
(l > 1)l(l>1)的环,
我们总可以得到一个长度为l-1l−1的LCS,
于是这个题的答案就很明显了, 就是nn减去长度大于11的环的数目.

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

const int maxn=1e5+10;

bool vis[maxn];

struct node

{

    int a,b;

}p[maxn];

bool cmp(node x,node y)

{

    return x.a<y.a;

}

int main()

{

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

    //freopen("o.txt","w",stdout);

    int T ;

    cin>>T;

    while(T--)

    {

        memset(vis,0,sizeof(vis));

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

        for(int i=1;i<=n;i++) scanf("%d",&p[i].a);

        for(int i=1;i<=n;i++) scanf("%d",&p[i].b);

        sort(p+1,p+1+n,cmp);

        int ans=0;

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

        {

            if(vis[i]) continue;

            vis[i]=1;

            if(p[i].a==p[i].b) ans++;

            else

            {

                int pos=p[i].b;

                while(!vis[pos])

                {

                    ans++;

                    vis[pos]=1;

                    pos=p[pos].b;

                }

            }

        }

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

    }

    //system("pause");

    return 0;

}

巴特西

HDU 5495：LCS

LCS

最新文章

热门文章