POJ 3356.AGTC

问题简述:

  输入两个序列x和y,分别执行下列三个步骤,将序列x转化为y

  (1)插入;(2)删除;(3)替换;

  要求输出最小操作数。

  原题链接:http://poj.org/problem?id=3356

解题思路:

  明显的动态规划题,输入两个字符串 a[0...m-1] , b[0...n]

  使用二维数组 dp[i,j] 记录 a[0...i] 和 b[0...j] 对应的最小操作数

  显然有以下递归方程:

  dp[i,0] = i

  dp[0,j] = j

  dp[i,j] = dp[i-1,j-1]     if a[i-1]==b[j-1]

  dp[i,j] = min(dp[i-1,j-1],dp[i-1,j],dp[i,j-1]) + 1    if a[i-1]!=b[j-1]

源代码

 1 /*
 2 OJ: POJ
 3 ID: 3013216109
 4 TASK: 3356.AGTC
 5 LANG: C++
 6 NOTE: DP
 7 */
 8 #include <cstdio>
 9
10 const int MAX=1005;
11 int m,n,i,j,k;
12 char a[MAX],b[MAX];
13 int dp[MAX][MAX],c[MAX];
14
15 int min(int x,int y,int z) {
16     if(x<+y&&x<=z)
17         return x;
18     if(y<=x&&y<=z)
19         return y;
20     if(z<=x&&z<=y)
21         return z;
22 }
23
24 int main()
25 {
26     while(scanf("%d %s",&m,a)!=EOF) {
27         scanf("%d %s",&n,b);
28         for(i=0;i<=m;i++)
29             dp[i][0]=i;
30         for(j=0;j<=n;j++)
31             dp[0][j]=j;
32         k=0;
33         for(i=1;i<=m;i++) {
34             for(j=1;j<=n;j++) {
35                 if(a[i-1]==b[j-1])
36                     dp[i][j]=dp[i-1][j-1];
37                 else
38                     dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
39             }
40         }
41         printf("%d\n",dp[m][n]);
42     }
43     return 0;
44 }
时间: 06-01

POJ 3356.AGTC的相关文章

POJ 3356 AGTC 最短编辑距离 DP

http://poj.org/problem?id=3356 题意: 给两个长度不大于1000的串,修改其中一个串使得两串相同,问最少修改次数.修改有三种,插入一个字符,删除一个字符,改变一个字符. 分析: 直接给方程. dp[i][j]表示第一个串前i位和第二串前j位匹配的最小修改次数. dp[0][0] = 0, dp[length(x)][length(y)]为答案. dp[i][j] = min(dp[i-1][j-1] + x[i] != y[j], dp[i-1][j] + 1, d

POJ 3356 AGTC(最长公共子序列)

AGTC 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 missin

POJ 3356 AGTC(DP-最小编辑距离)

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 

POJ 3356 AGTC(DP求字符串编辑距离)

给出两个长度小于1000的字符串,有三种操作,插入一个字符,删除一个字符,替换一个字符. 问A变成B所需的最少操作数(即编辑距离) 考虑DP,可以用反证法证明依次从头到尾对A,B进行匹配是不会影响答案的 令dp[i][j]表示A[i]~[lenA]变成B[j]~[lenB]的最优解. 如果把B[j]插入到A[i]前,dp[i][j]=dp[i][j+1]+1 如果删除A[i],dp[i][j]=dp[i+1][j]+1. 如果A[i]==B[j], dp[i][j]=dp[i+1][j+1].

poj 3356

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

POJ - 3186 Treats for the Cows (区间DP)

题目链接:http://poj.org/problem?id=3186 题意:给定一组序列,取n次,每次可以取序列最前面的数或最后面的数,第n次出来就乘n,然后求和的最大值. 题解:用dp[i][j]表示i~j区间和的最大值,然后根据这个状态可以从删前和删后转移过来,推出状态转移方程: dp[i][j]=max(dp[i+1][j]+value[i]*k,dp[i][j-1]+value[j]*k) 1 #include <iostream> 2 #include <algorithm&

POJ 2533 - Longest Ordered Subsequence(最长上升子序列) 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:http://poj.org/problem?id=2533 Description A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK)

POJ——T2271 Guardian of Decency

http://poj.org/problem?id=2771 Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 5932   Accepted: 2463 Description Frank N. Stein is a very conservative high-school teacher. He wants to take some of his students on an excursion, but he is

POJ——T2446 Chessboard

http://poj.org/problem?id=2446 Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 18560   Accepted: 5857 Description Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of c