【题目链接】：click here~~
【题目大意】：
Problem Description
. Both sequences are permutation of. You are going to find another permutationsuch that the length of LCS (longest common subsequence) ofis maximum.
Input
, indicating the number of test cases. For each test case:The first line contains an integer- the length of the permutation. The second line contains. The third line contains.The sum ofin the test cases will not exceed.
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
【思路】：题目中给出的是两个排列, 于是我们我们可以先把排列分成若干个环, 显然环与环之间是独立的. 事实上对于一个长度为l (l > 1)的环, 我们总可以得到一个长度为的LCS, 于是这个题的答案就很明显了, 就是的环的数目.
代码：
/** Problem: NO:HDU 5495* Running time: 764MS* Complier: G++* Author: javaherongwei* Create Time: 15:29 2015/10/4 星期日*/#include <math.h>#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;#define min(a,b) a<b?a:b#define max(a,b) a>b?a:btypedef long long LL;const double eps = 1e-8;const double pi = acos(-1.0);const int maxn = 1e5+10;inline LL read(){int c=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}return c*f;}int fa[maxn];int st[maxn],sb[maxn],sum[maxn];bool ok;int Find(int x){if(x==fa[x]) return x;return fa[x]=Find(fa[x]);}void Merge(int x,int y){int fx=Find(x);int fy=Find(y);if(fx==fy) return ;else fa[fx]=fy,sum[fy]+=sum[fx];//统计根节点以下元素个数}int main(){int t;t=read();while(t–){int n;n=read();for(int i=1; i<=n; ++i) st[i]=read();for(int i=1; i<=n; ++i) sb[i]=read();for(int i=1; i<=n; ++i) sum[i]=1,fa[i]=i;for(int i=1; i<=n; ++i){Merge(st[i],sb[i]);}int cnt=0;for(int i=1; i<=n; ++i){if(fa[i]==i){if(sum[i]==1) cnt++;else cnt+=sum[i]-1;}}printf("%d\n",cnt);} return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，第一个青春是上帝给的;第二个的青春是靠自己努力的
