LCS(HDU_5495 循环节)

题意：给出两个序列a_n和b_n，想在给出一个序列p_n，问经过a[p₁],,,,a[p_n]和b[p₁],,,b[p_n]变换后序列a和序列b的最长公共子序列的长度是多少。

思路：对a[i]->b[i]建边，最终总能形成一个环，对于这个长度为L的环，我们总能找到一个长度为L-1的LCS。所以，我们只要用序列的长度减去长度大于1的环的个数就是最终的结果。

例如：

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+;

typedef long long ll;

int a[maxn],b[maxn],c[maxn];

int vis[maxn];

inline void init()

{

    memset(vis,,sizeof(vis));

    return;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        init();

        int n;

        scanf("%d",&n);

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

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

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

        {

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

            c[a[i]] = b[i];

        }

        int ans = n;

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

        {

            int t = i;

            if(c[t] != t && !vis[t])

            {

                ans--;

                while(!vis[t])

                {

                    vis[t] = ;

                    t = c[t];

                }

            }

        }

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

    }

    return ;

}

/*

样例输入：

2

3

1 2 3

3 2 1

6

1 5 3 2 6 4

3 6 2 4 5 1

样例输出：

2

4

*/

巴特西

LCS(HDU_5495 循环节)

最新文章

热门文章