首页 > 代码库 > hdu-5495 LCS(置换)

hdu-5495 LCS(置换)

2024-08-15 05:11:44   223人阅读

题目链接：

LCS

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 818    Accepted Submission(s): 453


Problem Description
You are given two sequence {a1,a2,...,an} and {b1,b2,...,bn}. Both sequences are permutation of {1,2,...,n}. You are going to find another permutation {p1,p2,...,pn} such that the length of LCS (longest common subsequence) of {ap1,ap2,...,apn} and {bp1,bp2,...,bpn} is maximum.
 

 

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n(1≤n≤105) - the length of the permutation. The second line contains n integers a1,a2,...,an. The third line contains nintegers b1,b2,...,bn.

The sum of n in the test cases will not exceed 2×106.
 

 

Output
For each test case, output the maximum length of LCS.
 

 

Sample Input
231 2 33 2 161 5 3 2 6 43 6 2 4 5 1
 

 

Sample Output
24
 
题意：
 
问把数列重新排一下的LCS的长度是多少;
 
思路：
 
可以发现把置换分成循环后除长度为一的循环外,每个循环都可以变换最后形成l-1的LCS,所以就好了;
 
AC代码：
 
#include <bits/stdc++.h>using namespace std;const int maxn=1e5+10;int n,a[maxn],b[maxn],pos[maxn],vis[maxn];int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i,vis[i]=0;        for(int i=1;i<=n;i++)scanf("%d",&b[i]);        int ans=0;        for(int i=1;i<=n;i++)        {            if(!vis[b[i]])            {                vis[b[i]]=1;                int len=0,fa=b[i],p;                while(1)                {                    p=pos[fa];                    fa=b[p];                    len++;                    if(vis[fa])break;                    vis[fa]=1;                }                if(len==1)ans++;                else ans+=len-1;            }        }        printf("%d\n",ans);    }    return 0;}

　　

 

hdu-5495 LCS(置换)


联系
我们