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

· · 题解

P13788 题解：

主要思路：

::::info[为什么是 a 在 b 中的位置，而不是 b 在 a 中的位置？] 阅读题面可以发现，我们要求的是 a 的连续子段是否是 b 的子序列，不难发现存储 b 在 a 中的位置，再判断位置是否连续会比较好做。 ::::

dp_{b_i}=dp_{b_j}+1

其中 j<i 且 c_{b_i}-1=c_{b_j}。

于是就有了这样的 O(n^2) 暴力代码：

#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}。

::::info[为什么是 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：

#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;//完结撒花！！！
}

感谢阅读。

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