AGTC
Time Limit: |
|
Memory Limit: |
Total Submissions: |
|
Accepted: |
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 n
≥ m
.
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 AGTCTGACGC
11 AGTAAGTAGGC
Sample Output
4
设有长度
l1
和
l2
的字符串
s1
和
s2,res[i][j]
为
s1
的前
i
个字符变成
s2
的前
j
个字符所需的最少操作数
,
转移方程为
:
if (s1[i]==s2[j]) res[i+1][j+1]=min(res[i][j],res[i+1][j]+1,res[i][j+1]+1);
else res[i+1][j+1]=min(res[i][j]+1,res[i+1][j]+1,res[i][j+1]+1);
当
(s1[i]==s2[j])
时
,res[i+1][j+1]
可以直接取
res[i][j],
也可以从
res[i+1][j]
加
1
得到
,
也可以从
res[i][j+1]
得到
,
取其中的最小者便是当前的最优解
.
(s1[i]!=s2[j])
时相似
.
代码如下
: