本文共 2026 字，大约阅读时间需要 6 分钟。

题意：

第一行给出测试样例个数t。

每个测试样例中第一行输入n（两个数组给出的数字的范围是在1~n*n之间），p（第一个数组的元素个数为p+1），q（第二个数组的元素个数为q+1）

第二行输入第一个数组，第三行输入第二个数组。数组内没有任意两个数相同。且首位都是1。

求给定的两个数组的最长公共子序列长度。

这道题的数据范围很大，对于普通的O（n^2）的算法来讲，时间复杂度非常大。 

然而这道题有着特殊的条件，那就是没有任意两个数字是相同的。  那么我们可以考虑如果将b中数字在a中出现的位置替换为b的值，那么显然b的最长上升子序列LIS就是a和b的最长公共子序列LCS。    例如： a[7]={1,7,5,4,8,3,9} 位置: 1,2,3,4,5,6,7 b[8]={1,4,3,5,6,2,8,9}  将b的值替换  b[8]={1,4,6,3,0,0,5,7}（-1表示没出现过）  这时候从b中选出的所有不为-1数字都能保证是a,b的公共数字  然后再找出单调递增的数字就是ab公共的数字，并且是在a中从左到右顺序的公共序列。

代码：(最长公共子序列的O(nlogn)的解法:LCS转换为LIS）AC

#include
   
    #include
    
     #include
     
       #include
      
        #include
       
        #include
        
          using namespace std;const int maxn=65777;int lis[maxn],b[maxn],has[maxn];//lis存放公共子序列 b存放b序列数字在a序列中的位置 存放a序列中数字的位置int main(){ int t,n,p,q,x; scanf("%d",&t); for(int f=1;f<=t;f++) { memset(has,-1,sizeof(has)); scanf("%d%d%d",&n,&p,&q); for(int i=1;i<=p+1;i++) { scanf("%d",&x); has[x]=i; //将元素的下标存下来 } for(int i=1;i<=q+1;i++) { scanf("%d",&x); b[i]=has[x]; //b数列的数如果在a数列中存在，那么就存下来其在a数列的下标 } int ind=0; for(int i=1;i<=q+1;i++) { if(b[i]==-1)continue; if(ind==0) //第一个数，直接存入lis数组中 { ind++; lis[ind]=b[i]; continue; } else if(b[i]>lis[ind]) //如果b[i]大于lis数组中的最后一个数，直接存入lis数组中 { ind++; lis[ind]=b[i]; continue; } int tem=lower_bound(lis+1,lis+ind+1,b[i])-lis; //找到第一个大于或等于b[i]这个元素的位置 lis[tem]=b[i]; //更新成更小的值 } printf("Case %d: %d\n",f,ind); } return 0;}
        
       
      
     
    
   

WA的代码：(最长公共子序列的O(n^2)的解法)  

#include
   
    #include
    
     #include
     
       #include
      
        #include
       
        #include
        
          using namespace std;const int maxn=62510;int dp[maxn][maxn];int a[maxn],b[maxn];int main(){ int t,n,p,q,x; scanf("%d",&t); for(int f=1;f<=t;f++) { memset(dp,0,sizeof(dp)); scanf("%d%d%d",&n,&p,&q); for(int i=1;i<=p+1;i++) scanf("%d",&a[i]); for(int i=1;i<=q+1;i++) scanf("%d",&b[i]); int ans=0; for(int i=1;i<=p+1;i++) { for(int j=1;j<=q+1;j++) { if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); ans=max(ans,dp[i][j]); } } printf("%d\n",ans); } return 0;}
        
       
      
     
    
   

 

转载地址：http://dtzci.baihongyu.com/