hdu 5495 LCS

Problem Description

You are given two sequence {a1,a2,...,an} and {b1,b2,...,bn}. Both sequences are permutation of {,,...,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(≤n≤) - 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 ×.

 Output

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

Sample Input

 Sample Output

 SourceBestCoder Round #58 (div.2) 

题意：

给出1~n的两个排序a[n],b[n]，求用某个排序p[n]，使得a[p[0]],a[p[1]],a[p[2]]······与b[p[0]],b[p[1]],b[p[2]]······的最长公共子序列取得最大值，求最终取得的LCS多大。

思路：

LCS一定会tle的，关键就是这是1~n的序列，所以必然a[],b[]存在相同的数字，也就是一定会由一些循环节组成，而每个循环节经过排列首尾相接一定会有只相错一位的情况，最终的LCS也就是总长减去循环节的个数，特判自环不减就行了。直接深搜写的，跑得比较慢。

来自官方题解：

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

 #pragma comment(linker, "/STACK:1024000000,1024000000")
 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<math.h>
 #include<algorithm>
 #include<queue>
 #include<set>
 #include<bitset>
 #include<map>
 #include<vector>
 #include<stdlib.h>
 #include <stack>
 using namespace std;
 #define PI acos(-1.0)
 #define max(a,b) (a) > (b) ? (a) : (b)
 #define min(a,b) (a) < (b) ? (a) : (b)
 #define ll long long
 #define eps 1e-10
 #define MOD 1000000007
 #define N 100006
 #define inf 1e12
 int n;
 int a[N];
 int b[N];
 int vis[N];
 bool dfs(int x){
    int tmp=b[x];
    if(!vis[tmp]){
       vis[tmp]=;
       dfs(a[tmp]);
       return true;
    }
    return false;
 }
 int main()
 {
    int t;
    scanf("%d",&t);
    while(t--){
          memset(vis,,sizeof(vis));
          scanf("%d",&n);
          for(int i=;i<=n;i++){
              scanf("%d",&a[i]);
          }
          int x;
          for(int i=;i<=n;i++){
              scanf("%d",&x);
              b[x]=i;
          }
          int ans=;          for(int i=;i<=n;i++){
              if(!vis[i]){
                 vis[i]=;
                 if(!dfs(a[i])){
                    ans--;
                 }
                 ans++;
              }
          }
          printf("%d\n",n-ans);
    }
     return ;
 }