自动搬运

查看原文

来自洛谷，原作者为

	buzhidao 逃避者不配拥有未来. || 不蓝勾不改个签

搬运于2025-08-24 22:46:01，当前版本为作者最后更新于2023-06-28 15:45:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面传送门

题目分析

其实贪心不会超时，就是不能通过，详见这里。
这道题可以根据 $a,b$ 的填写顺序，列成一张表。图可能有点丑。 显然，我们要从左上角移动到右下角，把 $a,b$ 全部填写完。
我们只能向下或向右走。如果把所有路径都尝试一遍，就成了递归，必然超时。

所以我们需要——

动态规划

$dp$ 大小：$(n+1)\times(m+1)\times2$，最大占用 $200\text{MB}$ 空间，小于题目限制。
$dp_{i,j,0}$ 表示 $a$ 数组填写 $i$ 个数，$b$ 数组填写 $j$ 个数，$a$ 数组当前的最大值。
$dp_{i,j,1}$ 表示 $a$ 数组填写 $i$ 个数，$b$ 数组填写 $j$ 个数，$b$ 数组当前的最大值。

例如：
$a=(0),b=(0,0,1)$，已知 $dp_{0,3}=(0,5),dp_{1,2}=(6,4)$。目标：填充全部。可结合表格分析。

• 路径 $1$：从 $dp_{0,3}$ 开始填写：因为 $a_1 \ne b_3$，所以 $dp_{1,3}=(1,5)$。
• 路径 $2$：从 $dp_{1,2}$ 开始填写：因为 $b_3 \ne b_2$，所以 $dp_{1,3}=(6,5)$。

综上，因为要取最小值，所以得到答案 $=\min(\max(1,5),\max(6,5))=\min(5,6)=5$。

递推公式

$dp_{i,j}$ 初始化为 $(\inf,\inf)$。

当 $i \ne 0$：

• 当 $a_i=a_{i-1}$：$dp_{i,j,0}=\min(dp_{i,j,0},dp_{i-1,j,0}+2)$，否则 $dp_{i,j,0}=\min(dp_{i,j,0},dp_{i-1,j,0}+1)$。
• 当 $a_i=b_j$：$dp_{i,j,0}=\min(dp_{i,j,0},dp_{i-1,j,1}+2)$，否则 $dp_{i,j,0}=\min(dp_{i,j,0},dp_{i-1,j,1}+1)$。

当 $j \ne 0$：

• 当 $b_j=b_{j-1}$：$dp_{i,j,1}=\min(dp_{i,j,1},dp_{i,j-1,1}+2)$，否则 $dp_{i,j,1}=\min(dp_{i,j,1},dp_{i,j-1,1}+1)$。
• 当 $b_j=a_i$：$dp_{i,j,1}=\min(dp_{i,j,1},dp_{i,j-1,0}+2)$，否则 $dp_{i,j,1}=\min(dp_{i,j,1},dp_{i,j-1,0}+1)$。

AC代码

#include<bits/stdc++.h>
using namespace std;
int dp[5005][5005][2];
int n,m,a[5005],b[5005];
const int inf=1e9;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//IO优化 
	cin>>n;for(int i=1;i<=n;++i) cin>>a[i];
	cin>>m;for(int i=1;i<=m;++i) cin>>b[i]; 
	for(int i=0;i<=n;++i){
		for(int j=0;j<=m;++j){
			if(i==0&&j==0) continue;//这种情况不存在 
			dp[i][j][0]=inf;
			//为防止代码过长，加以适当简化 
			if(i){
				dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+1+(bool)(a[i]==a[i-1]));
				dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+1+(bool)(a[i]==b[j]));
			}
			dp[i][j][1]=inf;
			if(j){
				dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+1+(bool)(b[j]==b[j-1]));
				dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+1+(bool)(b[j]==a[i]));
			}
		}
	}
	cout<<min(dp[n][m][0],dp[n][m][1]);//输出最优方案 
	return 0;
}