https://atcoder.jp/contests/abc386/tasks/abc386_f
一个字符串长度为5e5的编辑距离。
注意到有次数限制K，实际上s的前i个字符，最多和t的前i-k和i+k个字符相匹配。
所以做O(sl * k)的dp即可

void solve(){
    int k;cin>>k;
    string s,t;
    cin>>s>>t;
    s = ' '+ s;
    t = ' '+ t;
    int sl = s.size(), tl = t.size();
    if(abs(sl-tl) > k) return cout<<"No"<<endl,void();

    vector<vector<ll>> dp(sl+1,vector<ll>(2*k+2,1e15));
    dp[0][k] = 0;
    for(int i=0;i<=sl;i++)
        for(int d = 0;d<=2*k;d++){
            int j = i + d - k;
            if(j<0 || j>tl) continue;
            if(i>0) dp[i][d] = min(dp[i][d],dp[i-1][d+1] + 1);
            if(j>0) dp[i][d] = min(dp[i][d],dp[i][d-1] + 1);
            if(i>0 && j>0) dp[i][d] = min(dp[i][d],dp[i-1][d] + (s[i]!=t[j]));
        }
    if(dp[sl][tl- sl + k] <= k)  cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}