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

本文共 2802 字,大约阅读时间需要 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
>a[i]; } cin>>n; for(int j=0;j
>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<

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

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

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月16日 03时06分46秒