A40229. 最优包含
填空题
困难
知识点
题目描述
最优包含
题目描述
我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。
给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T？
输入格式
输入两行，每行一个字符串。
第一行的字符串为 S，第二行的字符串为 T。
两个字符串均非空而且只包含大写英文字母。
输出格式
输出一个整数，表示答案。
数据范围
1≤|T|≤|S|≤1000
输入样例：
ABCDEABCD
XAABZ
输出样例：
3
参考答案
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
template <typename T> inline void read(T &x) {
x = 0; T f = 1;char s = getchar();
for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
x *= f;
}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i > (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e3+5;
char s[N], t[N];
int dp[N][N];// 前i个和包括了前j个要改几次
int main() {
scanf("%s %s", s + 1, t + 1);
int n = strlen(s+1), m = strlen(t+1);
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for(int i = 1; i <= n; ++i) {
dp[i][0] = 0;
for(int j = 1; j <= m && j <= i; ++j) {
if(s[i] == t[j]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + 1);
}
}
}
cout << dp[n][m] << endl;
}
上一题
下一题