盾盾的打字机

admin

【题目描述】

盾盾有一个非常有意思的打字机，现在盾哥要用这台打字机来打出一段文章。

由于有了上次的经验，盾盾预先准备好了一段模板A存在了内存中，并以此为基础来打出文章B。盾盾每次操作可以将内存中的某一个字符改成另一个字符，或者在某一个位置插入一个字符，或者删除某一个位置上的字符。另外，为了避免自己预存的模板太腿反而浪费时间，盾哥在所有操作之前会斟酌一下选择留下模板A的某一个最优的子串以保证操作次数尽量少（当然盾盾也可以全保留或一个都不留），这一步不计入操作次数。

试求盾盾要打出文章B的最少操作次数。

子串是指母串中连续的一段。

【输入数据】

输入包含多组数据。

对于每组数据，两行，分别表示A和B。

【输出数据】

每组数据一行，一个数，表示最少操作次数。

【输入样例】【输出样例】

【数据约定】

30% ：|A|, |B|<= 10

100% ：1<= |A|, |B| <= 1000, 数据组数<= 10, 输入的串中只包含小写字母

admin

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=1e3+10;
   
4. int f[N][N],lena,lenb,ans;
   
5. string a,b;
   
6. int main()
   
7. {
   
8.         freopen("drdrd.in","r",stdin);
   
9.         freopen("drdrd.out","w",stdout);
   
10.         while (cin>>a>>b)
    
11.                 {
    
12.                         memset(f,0x3f,sizeof(f));
    
13.                         lena=a.length(),lenb=b.length(),ans=99999999;
    
14.                         for (int i=0; i<=lena; i++)
    
15.                                 {
    
16.                                         f[i][0]=0;
    
17.                                         for (int j=0; j<=lenb; j++)
    
18.                                                 {
    
19.                                                         if(a[i]!=b[j]) f[i+1][j+1]=min(f[i+1][j+1],f[i][j]+1);
    
20.                                                         else f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);
    
21.                                                         f[i+1][j]=min(f[i+1][j],f[i][j]+1);
    
22.                                                         f[i][j+1]=min(f[i][j+1],f[i][j]+1);
    
23.                                                 }
    
24.                                 }
    
25.                         for (int i=0; i<=lena; i++) ans=min(ans,f[i][lenb]);
    
26.                         cout<<ans<<endl;
    
27.                 }
    
28.         return 0;
    
29. }

复制代码

admin

用状态f[i][j]表示第一个串到了第i位，第二个串到了第j为的最优值，转移就枚举下一位怎么做。
注意边界条件。