题解：AT_abc386_f [ABC386F] Operate K

题目洛谷
#

题目 AtCoder
#

思路：
#

动态规划。

计算出最小编辑距离，并检查其是否小于等于 $K$。

二维动态规划：
#

现在先考虑二维 $dp$ 数组的情况。

二维 $dp$ 数组时，$dp_{i,j}$ 表示将 $S$ 的前 $i$ 个字符转换为 $T$ 的前 $j$ 个字符所需的最小操作数。

然后考虑转移。

在动态规划中，$dp_{i,j}$ 表示将字符串 $S$ 的前 $i$ 个字符转换为字符串 $T$ 的前 $j$ 个字符所需的最小操作数。为了计算 $dp_{i,j}$，我们需要考虑三种可能的操作：删除、插入和替换。

具体来说：

删除：如果我们从 $S$ 中删除一个字符，那么 $dp_{i,j}$ 可以由 $dp_{i-1,j}$ 转移而来，因为删除一个字符后，$S$ 的前 $i-1$ 个字符需要转换为 $T$ 的前 $j$ 个字符，这一步对应的操作次数加 $1$。
插入：如果我们向 $S$ 插入一个字符，使得它与 $T$ 的第 $j$ 个字符匹配，那么 $dp_{i,j}$ 可以由 $dp_{i,j-1}$ 转移而来，因为插入一个字符后，$S$ 的前 $i$ 个字符需要转换为 $T$ 的前 $j-1$ 个字符，这一步对应的操作次数加 $1$。
替换：如果我们用 $T$ 的第 $j$ 个字符替换 $S$ 的第 $i$ 个字符，那么 $dp_{i,j}$ 可以由 $dp_{i-1,j-1}$ 转移而来，因为替换一个字符后，$S$ 的前 $i-1$ 个字符需要转换为 $T$ 的前 $j-1$ 个字符。如果 $S_{i-1}$ 已经等于 $T_{j-1}$，则不需要额外增加操作次数；否则，这一步对应的操作次数加 $1$。

因此，$dp_{i,j}$ 的值是上述三种情况中的最小值。

同时当两个字符串的长度差大于 $K$ 时，一定是不可能在 $K$ 步内让他们相同的。

现在写出的代码可以解决一些数据小的测试点了，但是数据大一点的话，二维 $dp$ 数组会炸内存，因此考虑优化内存。

优化为一维：
#

观察状态转移方程可以发现，计算 $dp_{i,j}$ 只需要用到 $dp_{i-1,j}$、$dp_{i,j-1}$ 和 $dp_{i-1,j-1}$ 这三个值。这意味着我们并不需要整个二维数组来存储所有的中间结果，只需要当前行和上一行的结果即可。

具体的：

定义两个一维数组 $dp$ 和 $dp2$，$dp2$ 是上一行的值，数组大小为 $m+1$。

优化成一维后转移方程也要发生改变。

只需要将使用了上一行数据的改为访问 $dp2$ 的就行了，举个例子，对于二维时的 $dp_{i-1,j}$ 现在应该访问 $dp2_{j}$。

对应没有访问上一行数据的直接访问 $dp$ 数组就行了，举个例子，对于二维时的 $dp_{i,j-1}$ 现在应该访问 $dp_{j-1}$。

为了防止转移错误，我们要保证 $m \le n$，如果当 $m > n$ 时，会导致初始化错误，注意这是在数组大小为 $m+1$ 的情况下。

现在代码如下：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL k;
string S,T;
//vector<vector<int> >dp(500050,vector<int>(500050));
int dp[500050];
void solve(string S,string T){
	int n=T.size(),m=S.size();
//	vector<vector<int> >dp(m+1,vector<int>(n+1));
	if(m>n){
		solve(T,S);
		return;
	}
	vector<int>dp(m+1);
	vector<int>dp2(m+1);
	for(int i=0;i<=m;i++)dp2[i]=0;
	for(int i=1;i<=n;i++){
		dp[0]=i;
		char ti=T[i-1];
		for(int j=1;j<=m;j++){
			char sj=S[j-1];
			int add=(ti==sj)?0:1;
			dp[j]=min({dp2[j]+1,dp[j-1]+1,dp2[j-1]+add});
		}
		swap(dp,dp2);
	}
	if(dp2[m]<=k){
		cout<<"Yes";
	}
	else cout<<"No";
}
int main(){
	cin>>k>>S>>T;
	solve(S,T);
	return 0;
}

现在发现不会超内存了，但是会超时，考虑优化动态规划的循环。

优化循环：
#

对于每一个字符的位置，我们只需要考虑在编辑距离范围内的子串部分，即 $\max(1,i-K)$ 到 $\min(m,i+K)$。

AC 代码：
#

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL k;
string S,T;
//vector<vector<int> >dp(500050,vector<int>(500050));
int dp[500050];
void solve(string S,string T){
	LL n=T.size(),m=S.size();
	if(abs(n-m)>k){
		cout<<"No";return;
	}
//	vector<vector<int> >dp(m+1,vector<int>(n+1));
	if(m>n){
		solve(T,S);
		return;
	}
	vector<int>dp(m+1);
	vector<int>dp2(m+1);
	for(int i=0;i<=min(m,k);i++)dp2[i]=i;
	for(LL i=1;i<=n;i++){
		dp[0]=i;
		char ti=T[i-1];
		for(LL j=max(1ll,i-k);j<=min(m,i+k);j++){
			char sj=S[j-1];
			int add=(ti==sj)?0:1;
			dp[j]=min({dp2[j]+1,dp[j-1]+1,dp2[j-1]+add});
		}
		swap(dp,dp2);
	}
	if(dp2[m]<=k){
		cout<<"Yes";
	}
	else cout<<"No";
	return;
}
int main(){
	cin>>k>>S>>T;
	solve(S,T);
	return 0;
}

AC 记录。

题目洛谷 #

题目 AtCoder #

思路： #

二维动态规划： #

优化为一维： #

优化循环： #

AC 代码： #