题解：P10043 [CCPC 2023 北京市赛] 广播

博客使用更佳：My blog

题目传送门

这道题是一个标准的 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;
}

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