P13788 题解：

主要思路：

用数组 $c$ 存储 $b$ 排列中的每个数在 $a$ 排列中的位置。

为什么是

a

在

b

中的位置，而不是

b

在

a

中的位置？

阅读题面可以发现，我们要求的是

a

的连续子段是否是

b

的子序列，不难发现存储

b

在

a

中的位置，再判断位置是否连续会比较好做。

我们设 $dp_{b_i}$ 为以 $b_i$ 结尾的在 $a$ 中出现过的子序列的数量，于是不难写出这样的状态转移方程：

dp_{b_i}=dp_{b_j}+1

其中

j<i

且

c_{b_i}-1=c_{b_j}

。

于是就有了这样的

O(n^2)

暴力代码：

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e6+7;
int n;
int a[N],b[N],c[N],dp[N];
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	int sum=n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(c[b[i]]-1==c[b[j]]){
				dp[b[i]]=dp[b[j]]+1;
				sum+=dp[b[i]];
			}
		}
	}
	cout<<sum;
	return 0;
}

交上去，获得

40

分。

那么问题又来了，怎么消掉内部循环？

我们不难发现，内部循环遍历时，只有一个

c_{b_j}

满足要求，其余的则都为不必要的操作，那我们就可以用

a_{c_{b_i}-1}

来代替上文的

c_{b_j}

。

为什么是

a_{c_{b_i}-1}

？

我们都知道，

c

数组存储的是

b

中的每个值在

a

中的位置，于是

c_{b_i}-1

的含义就是

b_i

在

a

中的上一个值的位置，于是这一坨的意思也就显而易见了。

知道了这些，我们就可以写出状态转移方程了！

dp_{b_i}=dp_{a_{c_{b_i}-1}}+1

代码实现：

定义一个变量存储最终答案，再用上文的状态转移方程求和就可以了。

~其实上文那一大坨放代码里也挺清晰的。~

AC Code：

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e6+7;
int n;
int a[N],b[N],c[N],dp[N];
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[a[i]]=i;//存储位置
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	int sum=0;//存最终答案
	for(int i=1;i<=n;i++){
		dp[b[i]]=dp[a[c[b[i]]-1]]+1;//状态转移方程
		sum+=dp[b[i]];
	}
	cout<<sum;
	return 0;//完结撒花！！！
}

感谢阅读。

写题解不易，留个赞再走吧！！！

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

文章操作

P13788 题解：

主要思路：

代码实现：

相关推荐

评论

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