85%做法：
动态规划。
首先重编号，BFS序变成1...n，然后DFS序相应重编号。
记pos[i]为i号点在DFS中的位置，即pos[d[i]]=i。
记F[l][r]表示BFS序中l...r号点相同高度时的高度和，G[l][r]表示BFS序中l...r号点相同高度的个数。
我们要寻找合法的k，使得[r+1][k]作为下一层，然后转移：
F[r+1][k]+=F[l][r]+G[l][r]
G[r+1][k]+=G[l][r]
我们要找到合法的k，k要满足以下条件：
(1)[l,r]在DFS序中的下一个一定在[1,k]中。
分析：
假设A∈[l,r]，那么A在DFS序中的下一个B只有下面3种情况：
这3种情况中，B的高度最多比A多1。
[k+1,N]的点应该在[r+1,k]那一层下面，如果[l,r]在DFS序中的下一个在[k+1,N]中，就会在[r+1,k]那一层乱入一个[k+1,N]的点，这样是违法的。
所以这个条件限制了[k+1,N]进入[r+1,k]那一层。
(2)r+1在DFS序中的上一个在[l,r]中。
如下面这种情况：
如果r+1在DFS序中的上一个不在[l,r]那么，r+1就不能另开一层了。
(3)[r+1,k]在DFS序中的位置是递增的。
是为了防止这种情况发生：
时间复杂度O（N^3)，然而实际上满足条件的k并不多，可以过85%的数据。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define re(i,a,b) for(i=a;i<=b;i++)
#define red(i,a,b) for(i=a;i>=b;i--)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define SF scanf
#define PF printf
#define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0); inline void clear(vector<int> *A,int a,int b){int i,j;A->clear();re(i,,a)re(j,,b)A[i].push_back();} inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
} const int maxN=; int N;
int d[maxN+],b[maxN+];
int bak[maxN+],pos[maxN+];
DB F[maxN+][maxN+],G[maxN+][maxN+];
DB sumF,sumG,ans; int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int i,j,k;
N=gint();
re(i,,N)d[i]=gint();
re(i,,N)b[i]=gint();
re(i,,N)bak[b[i]]=i;
re(i,,N)d[i]=bak[d[i]],b[i]=bak[b[i]];
re(i,,N)pos[d[i]]=i;
F[][]=1.0,G[][]=1.0;
re(i,,N)re(j,i,N)
{
if(G[i][j]==0.0)continue;
int t=;
re(k,i,j)upmax(t,d[pos[k]+]);
for(k=j+;k<=N;k++)
{
if(k<t)continue;
if(!(i<=d[pos[j+]-] && d[pos[j+]-]<=j))break;
if(k->=j+ && pos[k]<pos[k-])break;
F[j+][k]+=F[i][j]+G[i][j];
G[j+][k]+=G[i][j];
}
}
sumF=sumG=0.0;
re(i,,N)sumF+=F[i][N],sumG+=G[i][N];
ans=(sgn(sumG)==)?0.0:sumF/sumG;
PF("%0.3lf\n",ans);
}
100%做法：
动态规划。
首先重编号，BFS序变成1...n，然后DFS序相应重编号。
记pos[i]为i号点在DFS中的位置，即pos[d[i]]=i。
记h[i]为第i号点的期望高度。
容易知道h[1]为1，h[2]为2
我们按照BFS序从小到大枚举1到N，我们知道i号点和i-1号点高度相差0或1，且只能出现在下面蓝色框（i-1号点右边的兄弟），红色框（i-1号点左边兄弟的儿子，此时蓝色框为空）和绿色框中（i-1号点的儿子，此时蓝色框和红色框为空）。
1.pos[i-1]>pos[i]
i号点一定在红色框中，所以h[i]=h[i-1]+1
2.pos[i-1]<pos[i]
2.1 pos[i-1]+1!=pos[i]
i号点一定在蓝色框中。
如果i号点在绿色框中，那么i一定是i-1的第一个儿子，这样的话pos[i-1]+1=pos[i]，矛盾，所以i号点一定在蓝色框中。
所以h[i]=h[i-1]
2.2 pos[i-1]+1=pos[i]
考虑绿色框，我们想要i号点在绿色框中就必须保证蓝色框和红色框为空。怎么保证呢？就是[1..i-1]号点在DFS序中的下一个都在[1..i]中。
2.2.1 [1..i-1]号点在DFS序中的下一个都在[1..i]中。
这时候i号点既可以在绿色框中也也可以在蓝色框中，所以h[i]=h[i-1]或h[i]=h[i-1]+1
因为这两种情况等概率，所以h[i]=h[i-1]+0.5
2.2.2 [1..i-1]号点在DFS序中的下一个并不都在[1..i]中。
这时候i号点只能在蓝色框，所以h[i]=h[i-1]
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define re(i,a,b) for(i=a;i<=b;i++)
#define red(i,a,b) for(i=a;i>=b;i--)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define SF scanf
#define PF printf
#define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0); inline void clear(vector<int> *A,int a,int b){int i,j;A->clear();re(i,,a)re(j,,b)A[i].push_back();} inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
} const int maxN=; int N;
int d[maxN+],b[maxN+];
int bak[maxN+],pos[maxN+];
DB h[maxN+]; int main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int i;
N=gint();
re(i,,N)d[i]=gint();
re(i,,N)b[i]=gint();
re(i,,N)bak[b[i]]=i;
re(i,,N)d[i]=bak[d[i]],b[i]=bak[b[i]];
re(i,,N)pos[d[i]]=i;
int t=;
h[]=1.0;
upmax(t,d[pos[]+]);
h[]=2.0;
upmax(t,d[pos[]+]);
re(i,,N)
{
if(pos[i-]>pos[i])
h[i]=h[i-]+1.0;
else
if(pos[i-]+!=pos[i])
h[i]=h[i-];
else
if(t<=i)
h[i]=h[i-]+0.5;
else
h[i]=h[i-];
upmax(t,d[pos[i]+]);
}
PF("%0.3lf\n",h[N]);
return ;
}