题解：AT_abc386_f [ABC386F] Operate K

__Inv_day_in_R__ · 2025-01-02 21:30:17 · 题解

DP。看C题的时候就想到编辑距离这题，设计DP状态：dp(i,j) 表示 s 的前 i 个字符与 t 的前 j 个字符之间最少操作次数。如果最后一次使用替换字符，那么从 dp(i-1,j-1)+1 转移来，如果使用删除，那么从 dp(i,j-1)+1 转移来，如果使用插入，那么从 dp(i-1,j)+1 转移来，如果 s_i=t_j，还可以直接从 dp(i-1,j-1) 转移来。dp(i,j)=max\{dp(i-1,j-1)+[s_i\not=t_j],dp(i-1,j)+1,dp(i,j-1)+1\}

但是有一些不同，如数据范围 n\le5\times10^5，看似得用更快的做法，实际上操作次数大于 k 的，我们并不需要知道它们具体多少，压根不用算。观察到当 |i-j|>k 时，操作次数显然大于 k，只需开一个 f 数组，用 f(i,i-j) 表示 dp(i,j)（由于 i-j 可能是负数，真正实现时我额外加上了 22），f 数组开到 n\times45 就绝对够了。状态转移方程不变。

记得特判 \lvert\lvert s\rvert-\lvert t\rvert\rvert>k 的情况。

代码：

int k;
string s,t;
int f[500010][45];
int&dp(int i,int j){return f[i][i-j+22];}//通过传引用的方式实现dp与f的转化
void solve(){
    cin>>k>>s>>t;
    int n=s.size(),m=t.size();
    if(abs(n-m)>k){
        cout<<"No";
        return;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=k;i++){
        dp(0,i)=i;
        dp(i,0)=i;
    }
    for(int i=1;i<=n;i++)for(int j=max(1ll,i-k);j<=min(i+k,m);j++){
        dp(i,j)=min({dp(i-1,j)+1,dp(i,j-1)+1,dp(i-1,j-1)+(s[i-1]!=t[j-1])});
    }
    if(dp(n,m)<=k)cout<<"Yes";
    else cout<<"No";
}