自动搬运

查看原文

来自洛谷，原作者为

	Sparse_Table 太空桌子 && Twigbranch &&「我该在哪里停留？我问我自己。」

搬运于2025-08-24 22:54:08，当前版本为作者最后更新于2024-03-23 10:08:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

欢迎来我的博客玩。

题目传送门

这道题是一个标准的 dp 了，只不过它要倒序来做。

还是分三步。

1. 初值：初值想必都知道吧，若要求最小值，就把初值设成无穷大，$dp_{0,i}$ 和 $dp_{i,0}$ 都要设成 $i$，$dp_{0,0}$ 一定要赋值成 $0$，这是本人亲自犯过的错误QwQ。

2. 状态：$dp_{i,j}$ 表示 $a$ 数组的前 $i$ 个，$b$ 数组的前 $j$ 个变成可以广播的情况需要最小的操作次数。

3. 答案：只要有一个走到头时说明这种情况已经解决完毕，当 $i$ 是 $n$ 或者 $j$ 是 $m$ 时取最小值。

千万要把 $dp_{0,m}$，$dp_{n,0}$ 算上QwQ。

话不多说，直接上代码。

#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[2010], b[2010];
int dp[2010][2010];

int main() 
{
	memset(dp,0x3f,sizeof dp);
	cin >> n >> m;
	dp[0][0] = 0;
	for (int i = n; i >= 1; i--)
	{
		cin >> a[i];
		dp[i][0] = i;
	}
	for (int i = m; i >= 1; i--)
	{
		cin >> b[i];
		dp[0][i] = i;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if(a[i] == b[j] || a[i] == 1 || b[j] == 1) dp[i][j] = min({dp[i - 1][j - 1],dp[i][j - 1] + 1,dp[i - 1][j] + 1});
			else dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j - 1] + 1);
	int ans = 0x3f3f3f3f;
	for (int i = 0; i <= m; i++) ans = min(dp[n][i],ans);
	for (int i = 0; i <= n; i++) ans = min(dp[i][m],ans);
	cout << ans;
    return 0;
}

有兴趣的童鞋们可以挑战一下 编辑距离