题目
题目描述
盾盾有一个非常有意思的打字机，现在盾哥要用这台打字机来打出一段文章。
由于有了上次的经验，盾盾预先准备好了一段模板 $A$ 存在了内存中，并以此为基础来打出文章 $B$。盾盾每次操作可以将内存中的某一个字符改成另一个字符，或者在某一个位置插入一个字符，或者删除某一个位置上的字符。另外，为了避免自己预存的模板太腿反而浪费时间，盾哥在所有操作之前会斟酌一下选择留下模板 $A$ 的某一个最优的子串以保证操作次数尽量少（当然盾盾也可以全保留或一个都不留），这一步不计入操作次数。
试求盾盾要打出文章 $B$ 的最少操作次数。
子串是指母串中连续的一段。
输入格式
输入包含多组数据。
对于每组数据，两行，分别表示 $A$ 和 $B$。
输出格式
每组数据一行，一个数，表示最少操作次数。
输入输出样例
输入样例
1
2
3
4
5
6
aaaaa
aaa
abcabc
bcd
abcdef
klmnopq
输出样例
1
2
3
0
1
7
说明/提示
对于 $30\%$ 的数据，满足 $\vert A\vert,\vert B\vert\leq10$。
对于 $100\%$ 的数据，满足 $\vert A\vert,\vert B\vert\leq1000$，数据组数小于等于 $10$，且输入的串中只含有小写字母。
题解
很明显与字符串的编辑距离有关，不会的参见此处。
区别仅仅在于，本题可以选择一个子串开始转化。
选择一个子串，即可以从前面删去一段，再从后面删去一段。
参考编辑距离，设定状态 $dp_{i,j}$ 表示将 $a[1,i]$ 转化为 $b[1,j]$ 的最少方案数。
对于从前面删去一段，令 $f_{i,0}=0$ 即可。
令 $lena,lenb$ 分别表示字符串 $a,b$ 的长度，答案为：
\[\min\limits_{i=0}^{lena}dp_{i,lenb}\]$i$ 取小于 $lena$ 时即忽略了 $a[i+1,lena]$ 的部分。
AC 代码
时间复杂度：$\mathcal O\left(n^2\right)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1000;
char a[N+1+1],b[N+1+1],tmp[N+1+1];
int lena,lenb,dp[N+1][N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
while(~scanf("%s%s",a+1,b+1)){
lena=strlen(a+1);
lenb=strlen(b+1);
memset(dp,0,sizeof(dp));
for(int j=1;j<=lenb;j++){
dp[0][j]=j;
}
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;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]+(a[i]!=b[j]));
}
}
int ans=dp[lena][lenb];
for(int i=0;i<lena;i++){
ans=min(ans,dp[i][lenb]);
}printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
