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

本题显然是线性 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)$ 中小的那个，原因显而易见同上。

下面是代码部分。

CPP

#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;
}

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

文章操作

相关推荐

评论

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