处女座与复读机

刺骨的言语ヽ痛彻心扉 2021-12-15 08:47 252阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/327/G][https_ac.nowcoder.com_acm_contest_327_G]  
来源：牛客网

一天，处女座在牛客算法群里发了一句“我好强啊”，引起无数的复读，可是处女座发现复读之后变成了“处女座好强啊”。处女座经过调查发现群里的复读机都是失真的复读机，会固定的产生两个错误。一个错误可以是下面的形式之一：

1.       将任意一个小写字母替换成另外一个小写字母

2.       在任意位置添加一个小写字母

3.       删除任意一个字母

处女座现在在群里发了一句话，他收到了一个回应，他想知道这是不是一个复读机。

思路：

dp\[i\]\[j\]表示第i个字符变成j个字符的最小步数。

错误形式有3种：dp\[i\]\[j\]=min(dp\[i-1\]\[j\], dp\[i\]\[j-1\])+1;这是表示删除或者增加1个字符的情况。

dp\[i\]\[j\]=min(dp\[i\]\[j\], dp\[i-1\]\[j-1\]+(s\[i-1\]!=t\[j-1\]));便是错误一个字符

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 1005;
    char s[105], t[105];
    int dp[maxn][maxn];
    int n, m;
    
    int main()
    {
        cin >> s >> t;
        n = strlen(s);    m = strlen(t);
        for (int i = 0; i <= n; ++i)dp[i][0] = i;
        for (int i = 0; i <= m; ++i)dp[0][i] = i;
        for (int i = 1; i <= n;++i)
        for (int j = 1; j <= m; ++j)
        {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])+1;
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (s[i - 1] != t[j - 1]?1:0));
        }
        if (dp[n][m] <= 2)cout << "YES" << endl;
        else  cout << "NO" << endl;
    }

转载于:https://www.cnblogs.com/ALINGMAOMAO/p/10339606.html

[https_ac.nowcoder.com_acm_contest_327_G]: https://ac.nowcoder.com/acm/contest/327/G