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

yanxu_cn · 2025-07-24 16:36:58 · 题解

本题显然是线性 DP，复杂度是 O(nm)。DP 大致思路，分类讨论如下。

• 如果我们发现 p_i,q_j 两者相等或是其中有至少一个是 1，那么我们显然可以考虑继承 (i-1,j-1) 的状态，或者选择继承 (i,j-1) 或者 (i-1,j) 的状态并且补一个一！但是我们发现 (i,j-1) 或者 (i-1,j) 这个状态是不可能比 (i-1,j-1) 优的（本质上是由这个状态转移过去的，所以一定不够优），所以直接继承 (i-1,j-1) 的状态；
• 其余的情况，可以直接转移 (i,j-1)、(i-1,j) 中小的那个，原因显而易见同上。

下面是代码部分。

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    int m;
    constexpr int maxn = 2007;
    alignas(64)short a[maxn];
    alignas(64)short b[maxn];
    alignas(64)short dp[maxn][maxn];

    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] = dp[i-1][j-1];
            else
                dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j]+1);
        }
    }
    short ans = 30000;
    for(int i = 0;i<=m;++i)
        ans=min(ans,dp[n][i]);
    for(int i = 0;i<=n;++i)
        ans=min(ans,dp[i][m]);
    cout<<ans;
    return 0;
}