F-Operate-K

ACM 题解 DP

发布时间 : 2026-04-01 10:07

类似于编辑距离，但是数据范围5e5，n*m肯定爆
由于k <= 20 ，如果相差超过k，肯定不可行，所以转移约束
从max(1LL,i-k)到min(m,i+k)

整个转移是一个梯形

如果不判断，当长度max(1LL,i-k) > m，会直接break 时会导致前面的数据没有更新，会出现问题qwq

if (abs(n-m) > k) {
	cout << "No";
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int N = 5e5 + 10;
const int inf = 1e9;
vector<vector<int>> dp(3,vector<int>(N,inf));

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int k;
	cin >> k;
	string t, s;
	cin >> s >> t;

	int m = s.size(), n = t.size();
	if (abs(n-m) > k) {
		cout << "No";
		return 0;
	}	
	s = '0' + s;
	t = '1' + t;
	
	for (int i = 0; i <= min(m,k); i++) {
		dp[1][i] = i;
	}
	
	for (int i = 1; i <= n; i++) {
		dp[2][0] = i;
//		if (i - k - 1 >= 1) {
//			dp[2][i - k - 1] = inf;
//		}
		for (int j = max(1LL,i-k); j <= min(m,i+k); j++) {
			dp[2][j] = min({dp[1][j-1] + (t[i] != s[j]), dp[2][j-1] + 1, dp[1][j] + 1});
		}
		swap(dp[1],dp[2]);
	}
	
	if (dp[1][m] <= k) {
		cout << "Yes";
	} else {
		cout << "No";
	}
	
	return 0; 
}