AcWing 2553. 最优包含
原题链接
简单
作者:
ITNXD
,
2021-05-14 22:50:10
,
所有人可见
,
阅读 383
详细请查看注释
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
string a, b;
int f[N][N];
/*
状态表示;f[i][j]表示a的前i个字符包含b的前j个字符的最小操作步数!
状态计算:考虑是否使用a[i]进行匹配
1. 不使用a[i]:f[i][j] = f[i - 1][j]
2. 使用a[i]:
1. a[i] == b[j]:f[i][j] = f[i - 1][j - 1]
2. a[i] != b[j]:f[i][j] = f[i - 1][j - 1] + 1
*/
int main(){
cin >> a >> b;
a = ' ' + a, b = ' ' + b;
// 初始化:
memset(f, 0x3f, sizeof f);
// 前i个匹配前0个自然合法,且无需操作即可匹配!
for(int i = 0; i <= b.size(); i ++) f[i][0] = 0;
for(int i = 1; i <= a.size(); i ++)
for(int j = 1; j <= b.size(); j ++){
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[a.size()][b.size()] << endl;
return 0;
}