题目
LA 5052 Genome Evolution
题解
发现暴力是n^5，要优化到n^2,开始方了，但其实简单，，。其实也就是把一个串中的a[i]换成在另一个串中出现的位置pos[a[i]],然后就是找区间[i,j]使得这段区间内的数字是连续的，曾经见过这道题的树上模型，只需要 max{ a[k]|i<=k<=j}?min{ a[k]|i<=k<=j}+1==j?i+1 就可以了。很简单。
代码
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x) for(int i=x;i<=n;++i)
using namespace std;
const int maxn=3000+10;
inline int read(){int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret;
}int n,a[maxn],pos[maxn];
inline void solve()
{rep(i,1) pos[read()]=i;rep(i,1) a[i]=pos[read()];int M,m,cnt=0;for(int i=1,j;i<=n;++i)for(j=i+1,M=m=a[i];j<=n;++j)M=max(M,a[j]),m=min(m,a[j]),cnt+=(M-m==j-i);printf("%d\n",cnt);
}int main()
{freopen("std.in","r",stdin);while(scanf("%d",&n)==1&&n) solve();return 0;
}