poj3356---AGTC
发布日期:2022-02-02 02:58:13 浏览次数:6 分类:技术文章

本文共 2855 字,大约阅读时间需要 9 分钟。

Description

Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:

  • Deletion: a letter in x is missing in y at a corresponding position.
  • Insertion: a letter in y is missing in x at a corresponding position.
  • Change: letters at corresponding positions are distinct

Certainly, we would like to minimize the number of all possible operations.

Illustration
A G T A A G T * A G G C| | |
   |   |   | |A G T * C * T G A C G C
Deletion: * in the bottom line
Insertion: * in the top line
Change: when the letters at the top and bottom are distinct

This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like

A  G  T  A  A  G  T  A  G  G  C|  |  |
|
 |
 |  |A  G  T  C  T  G  *  A  C  G  C

and 4 moves would be required (3 changes and 1 deletion).

In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where nm.

Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.

Write a program that would minimize the number of possible operations to transform any string x into a string y.

Input

The input consists of the strings x and y prefixed by their respective lengths, which are within 1000.

Output

An integer representing the minimum number of possible operations to transform any string x into a string y.

Sample Input

10 AGTCTGACGC11 AGTAAGTAGGC

Sample Output

4
题目大意: 给出两个字符串x 与 y,其中x的长度为n,y的长度为m,并且m>=n
然后y可以经过删除一个字母,添加一个字母,转换一个字母,三种操作得到x
问最少可以经过多少次操作


解题思路:类似于最长公共子串
我们设dp[i][j]的意义为y取前i个字母和x取前j个字母的最少操作次数

那么可以得到dp[0][i] = i和dp[i][0]=i,因为某一字符串为空的,要得到另一个i长度字符串,必须经过i次插入操作。
而dp[1][1],有3中操作,
1.转换 ,将str1[0]和str2[0]判断,如果相等,则dp[1][1]=0,否则dp[1][1]=1
2.删除,因为,目的串比源串小,所以删除源串一个字符,
也就是必须有一次操作,删除str1[0]后,那么dp[1][1]就是dp[0][1]的值+1
3.添加,在目的串添加一个字符,即源串不变,但是目的串减1,和源串去匹配,即dp[1][0] + 1

这样dp[i][j]可以得到3中操作的最小值
dp[i-1][j-1]+str1[i]==str2[j]?0:1
dp[i-1][j]+1
dp[i][j-1]+1

代码实现:

#include 
   
    #include 
    
     using namespace std;char a[10001],b[10001];int dp[10001][10001];int main(){
     
int m,n;
cin>>m;
for(int i=0;i
{
cin>>a[i];
}
cin>>n;
for(int j=0;j
{
cin>>b[j];
}
dp[0][0]=0;
for(int i=1;i<=max(m,n);i++)
{
dp[0][i]=i;
dp[i][0]=i;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j]+1,dp[i][j-1]+1));
}
else
{
dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
cout<
return 0;}


转载地址:https://blog.csdn.net/u010368749/article/details/20943105 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:hdu1686--Oulipo
下一篇:uva111---History Grading

发表评论

最新留言

不错!
[***.249.68.14]2022年05月22日 12时22分45秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章