P2138 小Z的关系距离 题解

Math_rad_round · 2022-02-09 09:04:34 · 题解

为讨论方便，我们令下文中 |a|\geq|b|

对 a、b，如果它们各自删除不超过其自身长度一半的字符能够相等 也就意味着 a 剩下的字符串和 b 剩下的字符串是相等的，即:

距离为 1 等价于 最长公共子序列长度 \geq\frac{|a|}{2}

同时也可以推断出，如果我们在 b 中随便插入

那么我们可以不断地往 b 上插入 |b| 个字符，也就使最长公共子序列长度增加了 |b|，同时 |b| 也翻了一倍

直到最长公共子序列长度达到 \frac{|a|}{2} ，这时只需要再有一次操作即可完成

时空复杂度均为 O(|a||b|)，也就使求最长公共子序列。

注意：两字符串相等时答案为 1

代码：

#include<iostream>
using namespace std;
string a,b;
int f[300][300];
int main(){
    cin>>a>>b;
    int n=a.length(),m=b.length();
    if(n<m){
        swap(n,m);swap(a,b);
    }
    if(a==b){//特判相等 
        cout<<"1";return 0;
    }
    int ans=0;
    for(int i=1;i<=n;i++){//求最长公共子序列
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i-1]==b[j-1])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            ans=max(f[i][j],ans);
        }
    }
    int cnt=0;
    while(ans*2<n){
        cnt++;ans+=m;m+=m;
    }cnt++;
    cout<<cnt;
    return 0;
}