P6820

LYY_yyyy · 2024-01-13 14:35:33 · 题解

首先考虑 O(n^2) 的 dp。记录 f_{i,j} 表示完成第一个数列中的前 i 位和第二个数列中的前 j 位的最小代价。转移：

若 a_i=b_j，f_{i,j}=\min(f_{i-1,j},f_{i,j-1})+1

否则，f_{i,j}=f_{i-1,j-1}+1

然后我们注意到两个数列都是排列。这就意味着，对于每一个 i，只会有一个 j 进行第一个转移。然后我们又注意到第二个转移形如一个平移的形式，这就启发我们将空间压成一维，每次维护一个平移操作以及一个单点修改的操作。具体地，我们只需要完成平移、全局加一、单点修改操作即可。这可以通过将数组倍长，维护全局增量解决。之后再在数组上修改 i 对应的 j 的位置即可。时空复杂度 O(n)。代码很短，不到 500B。实现的时候注意上一版和这一版中全局增量的统一。

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],p[1000010];
int dp[2000010];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;int op;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>op,p[op]=i;
    for(int i=n;i<=2*n;i++) dp[i]=i-n;
    for(int i=1;i<=n;i++)
    {
        int l=n-i;
        dp[p[a[i]]+l]=min(dp[p[a[i]]+l+1],dp[p[a[i]]+l-1]+1);
    }cout<<dp[n]+n;
    return 0;
}