题目链接:点击进入 刚看到这题目还以为又碰到水题了,结果写了个O(n^2)的代码交上去超时了,才发现n有250*250那么大.后面在网上找到了一个nlgn求最长上升子序列的方法,才过了.这个nlgn算法的主要思想是将最长公共子序列转成最长上升子序列,然后用最长上升子序列nlgn的算法求解.更具体的解释可以参看这篇博文:最长公共子序列(nlogn)
代码如下:
;int const maxn=252*252;int a[maxn],b[maxn],c[maxn*10];int dp[maxn],d[maxn];int main(){//freopen(“in.txt”,”r”,stdin);int t,Case=0;int n,k1,k2;scanf(“%d”,&t);while(t–){scanf(“%d%d%d”,&n,&k1,&k2);++k1; ++k2;memset(dp,0,sizeof(dp));for(int i=1;i<=k1;i++)scanf(“%d”,&a[i]);for(int i=1;i<=k2;i++)scanf(“%d”,&b[i]);for(int i=1;i<=k2;i++)d[a[i]]=i;int cnt=0,len=0;dp[0]=0;for(int j=1;j<=k2;j++)c[j]=d[b[j]];for(int i=1;i<=k2;i++) ///以下为nlgn求最长上升子序列{if(c[i]>dp[len])dp[++len]=c[i];else{int k=lower_bound(dp,dp+len+1,c[i])-dp;dp[k]=c[i];}}printf(“Case %d: %d\n”,++Case,len);} return 0;}
，一个人，一条路，人在途中，心随景动，
