permu
[Description]
给定两个1~N的全排列A,B。有两个指针q和p，一开始q、p都为0，可执行以下三种操作：
1.q+1；2.p+1；3.q+1且p+1（Aq+1≠Bp+1时才可以这么做）。
[Hint]
<=1000000
f[i][j]代表p指i,q指j的时候还需要多少步才能到终点
30分转移:f[i][j]=f[i+1][j+1]+1(a[i+1]!=a[j+1]） f[i][j]=min(f[i+1][j],f[i][j+1])+1.
题目中有一个性质。。然而之前并没看到。。A和B数组是1-n的全排列
然后意思就是 f[i][j]=min(f[i+1][j],f[i][j+1])+1 这种转移最多n次
第一种转移，我们可以简单地用队列处理：先将f[n][0~n]存在队列中，然后将f[n][0]出队，将f[n][1~n]++，变成f[n-1][0~n-1]，再往队尾添加f[n-1][n]，对f[i+1][0~n]转移到f[i][0~n]的情况亦然。
但这只是能解决第一种转移，第二种转移需要另作处理。对于f[i+1][0~n]到f[i][0~n]的转移，如果a[i+1]==b[j+1]，f[i+1][j+1]就无法通过第一种转移转移到f[i][j]。对每个i，也存在且仅存在一个j，使得f[i][j]无法进行第一种转移。
对于第二种转移我们可以这样简化：
因为a[i+1]==b[j+1]，所以a[i+1]!=b[j]，所以f[i][j-1]==f[i+1][j]+1。
所以f[i][j]=min{f[i][j-1],f[i][j+1]+1} (a[i+1]==b[j+1])
有了这个方程，就可以在第一种转移完成后，找到使得a[i+1]==b[j+1]的j，取f[i][j]为队列中其前驱元素的值与其后继元素的值加1的较小值为f[i][j]的值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> #define maxn 1000001 using namespace std; inline int in()
{
int x=,f=;char ch=getchar();
while((ch<''||ch>'')&&ch!='-')ch=getchar();
if(ch=='-')ch=getchar(),f=-;
while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();
return f*x;
} int q[maxn*],fpos[maxn],a[maxn]; int main()
{
freopen("permu.in","r",stdin);
freopen("permu.out","w",stdout);
int n,u,head=,tail;
n=in();
tail=n;
for(int i=;i<=n;i++)a[i]=in();
for(int i=;i<=n;i++)u=in(),fpos[u]=i;
for(int i=;i<=n;i++)q[i]=n-i;
for(int i=n;i;i--){
int t=fpos[a[i]];head++;
q[head+t-]=min(q[head+t-],q[head+t]+);
q[++tail]=;
}
printf("%d",q[head]+n);
return ;
}