题目链接：
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
2
3
1 2 3
3 2 1
6
1 5 3 2 6 4
3 6 2 4 5 1
3
1 2 3
3 2 1
6
1 5 3 2 6 4
3 6 2 4 5 1
Sample Output
2
4
4
题意：
问把数列重新排一下的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;
}