题解：AT_abc386_f [ABC386F] Operate K

封面

题目洛谷

题目 AtCoder

思路：

动态规划。

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

二维动态规划：

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

二维 dpdp 数组时，dpi,jdp_{i,j} 表示将 SS 的前 ii 个字符转换为 TT 的前 jj 个字符所需的最小操作数。

然后考虑转移。

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

具体来说：

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

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

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

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

优化为一维：

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

具体的：

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

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

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

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

为了防止转移错误，我们要保证 m≤nm \le n，如果当 m>nm > n 时，会导致初始化错误，注意这是在数组大小为 m+1m+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)\max(1,i-K) 到 min⁡(m,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 记录。