题目链接：http://noi.openjudge.cn/ch0206/2988/
题解：
首先，题目有误，少了一个添加操作
和求解LCS之类的思路类似
f[i][j]表示a序列中1..i的部分和b序列中1...j的部分的编辑距离，得：
（1）i==0，j==0时，f[i][j]=0；
（2）i==0，j>0时，f[i][j]=j；j==0，i>0时，f[i][j]=i；即需要对空串进行i或j个添加操作；
（3）否则，f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+check(i,j))；（check函数：ai==bj返回1否则0）
<1>默认a[1...i-1]和b[1...j]已经处理好时，只需要在ai-1后添加一个bj使a[1...i]与b[1...j]相同
<2>默认a[1...i]和b[1...j-1]已经处理好时，只需要在bj-1后添加一个ai使a[1...i]与b[1...j]相同
<3>默认a[1...i-1]和b[1...j-1]已经处理好时，如果ai==bj，即不需要进行操作，否则需要对ai或者bj进行一次修改操作，使a[1...i]与b[1...j]相同
1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 1010 4 int lena,lenb,f[MAXN][MAXN]; 5 char a[MAXN],b[MAXN]; 6 inline int min(int x,int y) 7 { 8 return x<y?x:y; 9 } 10 bool check(int x,int y) 11 { 12 return a[x]==b[y]?true:false; 13 } 14 int main() 15 { 16 int T; 17 scanf("%d ",&T); 18 while(T--) 19 { 20 memset(f,0,sizeof(f)); 21 scanf("%s%s",a+1,b+1); 22 lena=strlen(a+1);lenb=strlen(b+1); 23 for(int i=1;i<=lena;++i)f[i][0]=i; 24 for(int i=1;i<=lenb;++i)f[0][i]=i; 25 f[0][0]=0; 26 for(int i=1;i<=lena;++i) 27 { 28 for(int j=1;j<=lenb;++j) 29 { 30 f[i][j]=min(min(f[i-1][j],f[i][j-1])+1,f[i-1][j-1]+!(check(i,j))); 31 } 32 } 33 printf("%d ",f[lena][lenb]); 34 } 35 return 0; 36 }