首页 > 代码库 > hoj_10411_二维DP

hoj_10411_二维DP

2024-07-06 19:35:58   223人阅读

字符串的修改
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 245, Accepted users: 231
Problem 10411 : No special judgement
Problem description

设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。
对任给的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。

Input
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于200。

Output
只有一个正整数，为最少字符操作次数。

Sample Input
sfdxbqw
gfdgw
Sample Output
4

 

  其实这道题道现在还是没有很好的理解，大致思路：对于a，b两个字符串：

 

   if(a[i-1]==b[j-1]) t[j]=p[j-1];  //此时为前一状态

   else t[j]=min(min(t[j-1],p[j-1]),p[j])+1;  //删除、插入、修改三个方向上最少的操作次数

   p[]保存的是上一行的最少操作次数，t[]保存当前的，每经过一轮循环那么就把t[]赋值给p[]，然后再重复操作，在此为滚动数组用法~~~

 

   最后，右下角的就是所求的~~~

 

i a[] s  f d x b q w
b[] 0 1 2 3 4 5 6 7
 g 1 1  2 3  4 5  6  7 
 f 2 2  1  2  3  4  5  6 
 d 3 3  2  1  2  3  4  5 
 g 4 4  3  2  2  3  4  5 
 w 5 5  4  3  3  3  4  4 

 

 AC代码：

 

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 int main()
11 {
12     int m, n;
13     char a[205], b[205];
14     int p[205], t[205];
15 
16     gets(a);
17     gets(b);
18 
19     m=strlen(a);
20     n=strlen(b);
21 
22     for(int i=0; i<=n; i++)  p[i]=i;  // i
23 
24     for(int i=1; i<=m; i++)  // m
25     {
26         for(int j=0; j<=n; j++) {  // t[j]
27 
28             if(j==0)  t[j]=i;  //
29 
30             else {
31 
32                 if(a[i-1]==b[j-1])  t[j]=p[j-1];
33                 else t[j]=min(min(t[j-1],p[j-1]),p[j])+1;  // min;
34             }
35         }
36 
37         for(int j=0; j<=n; j++)  p[j]=t[j];
38     }
39 
40     printf("%d\n",t[n]);
41 
42     return 0;
43 }

 

 

 


联系
我们