自动搬运

查看原文

来自洛谷，原作者为

	LYY_yyyy **

搬运于2025-08-24 22:24:19，当前版本为作者最后更新于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;
}