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

Sparse_Table · 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;
}

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