POJ 3356. AGTC

Author: 2015-10-09

ACM

, ,

1. 题目

http://poj.org/problem?id=3356

AGTC
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10970 Accepted: 4217

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

Source

Manila 2006

2. 思路

给出两个字符串（碱基序列）x和y，通过对x中的字符进行删除、插入、修改三种操作，使得x和y相同，求对x的最少操作数。

区间DP。记x和y的长度分别为lx和ly，第i个字符分别为x[i]和y[i]，使用f[i][j]表示将x的前i个字符变成y的前j个字符所需的最少操作数，有：

f[0 : lx][0] = 0 : lx
f[0][0 : ly] = 0 : ly
for i = 1 : lx
    for j = 1 : ly
        f[i][j] = min(
            f[i - 1][j - 1] + (x[i] == y[j] ? 0 : 1),
            f[i - 1][j] + 1,
            f[i][j - 1] + 1)

要把x的前i个字符变成y的前j个字符，有三种情况：

  • 如果x[i]和y[j]相同，则f[i][j] = f[i – 1][j – 1] ，否则将x[i]修改为y[j]，在f[i – 1][j – 1]基础上增加一步操作，f[i][j] = f[i – 1][j – 1] + 1 。
  • 在x[1 : i – 1]的基础上增加一个与y[j]相同的字符，f[i][j] = f[i – 1][j] + 1 。
  • 删除x[i]，f[i][j] = f[i][j – 1] + 1 。

f[i][j]为以上三种情况的最小值。

3. 代码

#include <cstdio>

const int MAX_LENGTH = 1000 + 10;

void solveE7c_AGTC();

int main() {
	solveE7c_AGTC();
	return 0;
}

char x[MAX_LENGTH], y[MAX_LENGTH];
int f[MAX_LENGTH][MAX_LENGTH];
void solveE7c_AGTC() {
	while (1) {
		int xLen, yLen;
		if (scanf("%d %s", &xLen, x) != 2)
			break;
		scanf("%d %s", &yLen, y);

		for (int i = 0; i < MAX_LENGTH; ++i) {
			f[i][0] = i;
			f[0][i] = i;
		}

		for (int i = 1; i <= xLen; ++i) {
			for (int j = 1; j <= yLen; ++j) {
				int cand1 = f[i - 1][j - 1],
					cand2 = f[i - 1][j] + 1,
					cand3 = f[i][j - 1] + 1;

				if (x[i - 1] != y[j - 1]) {
					++cand1;
				}
				f[i][j] = cand1 < cand2 ? cand1 : cand2;
				f[i][j] = f[i][j] < cand3 ? f[i][j] : cand3;
				// printf("%c %d %c %d %d\n", x[i - 1], i, y[j - 1], j, f[i][j]);
			}
		}

		printf("%d\n", f[xLen][yLen]);
	}

}