题解：P13788 「CZOI-R6」Permutation and Subsequence

题意

你需要求出有多少个

a

的非空连续子段是

b

的子序列。

分析

把

a

按照

1,2,3,...,n

的顺序映射，

b

更

a

一起映射，因为

a

是排列，所以数组即可。

原因：简化问题

现在只需要在

b

中找连续的求数量即可，用

DP

解决。

具体见代码。

Code

CPP

#include<bits/stdc++.h>
using namespace std; 
#define int long long
const int N=1e6+5,inf=1e14;
int n;
int a[N],b[N],c[N],d[N];
int dp[N],ans;
//dp[i]=表示b中第i个数连续的数量
//dp[i]=dp[d[b[i]-1](i表示的数的上一个)]+1 预处理d
//all=0
//ans=sum(dp)
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],c[a[i]]=i,a[i]=i;//用数组映射a
    for(int i=1;i<=n;i++)
        cin>>b[i],b[i]=c[b[i]],d[b[i]]=i;//预处理d
    for(int i=1;i<=n;i++){
        dp[i]+=dp[d[b[i]-1]]+1;ans+=dp[i];
    }
    cout<<ans;
    return 0;
}
/*
old:
3 5 2 4 1
2 4 5 3 1 

new:
1 2 3 4 5
3 4 2 1 5
*/

题解：P13788 「CZOI-R6」Permutation and Subsequence

文章操作

题意

分析

Code

相关推荐

评论

题解：P13788 「CZOI-R6」Permutation and Subsequence