LA 5052 Genome Evolution (思维)

本文主要是介绍LA 5052 Genome Evolution (思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LA 5052 Genome Evolution

题目大意:

给1~n的两个排列A,B,统计有多少个子集A,B均有,子集要满足是连续序列,且至少包含两个元素.(1<=n<=5000)

题目分析:

对于两个子集,要满足元素相同,且是连续序列,则长度要一致.
若确定某一个点i为在A序列中的右边界,那么A序列中每往左加入一个元素j,在B中也会对应有一个位置.显然此时能满足元素相同的要求.
那么还需要是连续序列,若在B中的元素最左边在L,最右边在R.若R-L+1==i-j+1,即两序列的长度一致,则B中形成序列是连续序列.

代码

#include<cstdio>
#include<iostream>
#include<algorithm>using namespace std;const int maxn=3000+10;int A[maxn],B[maxn],pos[maxn],n;int main()
{while(scanf("%d",&n)==1&&n) {for(int i=0;i<n;i++) scanf("%d",&A[i]);for(int i=0;i<n;i++) scanf("%d",&B[i]),pos[B[i]]=i;//记录下每个数在B中对应位置 int ans=0;for(int i=1;i<n;i++) {int L=pos[A[i]],R=pos[A[i]];for(int j=i-1;j>=0;j--) {L=min(L,pos[A[j]]);R=max(R,pos[A[j]]);if(R-L+1==i-j+1) ++ans;}}printf("%d\n",ans);}return 0;
}

这篇关于LA 5052 Genome Evolution (思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---