2019第十届蓝桥杯国赛-F最优包含

2021-07-03 · 23次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #动态规划

题面

【问题描述】

我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。

给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T ？

【输入格式】

输入两行，每行一个字符串。第一行的字符串为 S，第二行的字符串为 T。两个字符串均非空而且只包含大写英文字母。

【输出格式】

输出一个整数，表示答案。

【样例输入】

ABCDEABCD
XAABZ

【样例输出】

【评测用例规模与约定】

对于 20% 的评测用例， $1 \le |T| \le |S | \le 20$ ；

对于 40% 的评测用例， $1 \le |T| \le |S | \le 100$ ；

对于所有评测用例， $1 \le |T| \le |S | \le 1000$ 。

思路

动态规划，时间复杂度 $O(|T|\times|S|)$ 。

$f[i][j]$ 表示使 s 的前 i 个字符包含 t 中的前 j 个字符，所需要修改最小操作数，其状态转移方程如下：

$f[i][j] = \begin{cases} j, & i = 0 \\ 0, & j = 0 \\ f[i-1][j-1], & s[i - 1] = t[j - 1] \\ f[i-1][j], & s[i-1] \ne t[j-1] \\ min(f[i-1][j-1], f[i-1][j]), & s[i-1] \ne t[j-1]{\text{ }}and {\text{ }} i-1 \ge j \end{cases}$

$f[m][n]$ （m 和 n 分别为s 和 t 的长度）即为最终答案。

代码

#include<iostream>
#include<string>
#include<cstring>

using namespace std;
const int N = 1005;
int f[N][N];
string s, t;

int main() {
    while (cin >> s >> t) {
        int m = s.length();
        int n = t.length();

        memset(f, 0x3f, sizeof f);
        for (int j = 1; j <= n; j++) f[0][j] = j;
        for (int i = 0; i <= m; i++) f[i][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s[i - 1] == t[j - 1]) f[i][j] = f[i - 1][j - 1];
                else {
                    if (i - 1 >= j) f[i][j] = min(f[i][j], f[i - 1][j]);
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }

        cout << f[m][n] << endl;
    }

    return 0;
}

标题：	2019第十届蓝桥杯国赛-F最优包含
链接：	https://www.fightingok.cn/detail/117
更新：	2022-09-18 22:40:19
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可