POJ——3356 ACGT

短命女 2022-08-11 03:23 27阅读 0赞

题意：

给定原字符串和目标字符串，有三种操作方法，转变、添加、删除字符；求得到目标字符串的最小操作数。

如题目中的示例最小操作数为4，不过这一题在poj上的测试数据比较水，用最长公共子序列也能轻松水过，不过那种方法是错的。

如：  
6 ATGCGC  
6 GCCGAT

实际最小操作数为5，而用哪种方法则得到3；

其实本来我也是打算用哪种犯二的方法做的，可惜没多组，仔细考虑了一下，发现哪种方法不可以，于是等模拟赛结束了就再回头考虑的这一题，参考了别人的题解；

这一题思路同最长公共子序列类似，用二维数组存储，模拟最小操作数。

才c\[i-1\]\[j-1\],c\[i-1\]\[j\],c\[i\] \[j-1\]为满足当前规模要求的最小操作数。

求c\[i\] \[j\]:

1.如果s1\[i\] ==s2\[j\],则有c\[i-1\]\[j-1\]待取，不用操作;

2.如果不等，c\[i-1\]\[j\]+1;插入一个字母满足要求

3.c\[i\]\[j-1\]+1也是待取值，同样在满足前面的前提下，插入一个数满足要求。

c\[i\]\[j\]取三个中的最小值。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    using namespace std;
    int c[1000][1000];
    int main()
    {
    	char s1[1000],s2[1000];
    	int len1,len2,i,j;
    	while(scanf("%d%s%d%s",&len1,s1,&len2,s2)==4)
    	{
    		for(i=0;i<=len1;i++)c[0][i]=i;
    		for(i=0;i<=len2;i++)c[i][0]=i;
    
    		for(i=1;i<=len1;i++)
    			for(j=1;j<=len2;j++)//取到len2是因为这是目的串的长度。

{
    				int tmp=1;
    				if(s1[i-1]==s2[j-1])tmp=0;
    				tmp+=c[i-1][j-1];
    				tmp=min(c[i-1][j]+1,tmp);
    				c[i][j]=min(c[i][j-1]+1,tmp);
    			}
    			printf("%d\n",c[len1][len2]);
    	}	
    			
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3356 AGTC （最长公共子序列）

Let x and y be two strings over some finite alphabet A. We would like to transform x int

朴灿烈づ我的快乐病毒、/ 2024年02月17日 19:42/ 0 赞/ 34 阅读

相关 poj 1064 java_poj1064

Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15127 Accept

r囧r小猫/ 2022年11月05日 03:30/ 0 赞/ 226 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 242 阅读

相关 pku 3356 AGTC

\include <iostream> \include <string> using namespace std; int v\[1001\]\[1001\]; int ma

客官°小女子只卖身不卖艺/ 2022年08月13日 17:40/ 0 赞/ 39 阅读

相关 POJ——3356 ACGT

题意：给定原字符串和目标字符串，有三种操作方法，转变、添加、删除字符；求得到目标字符串的最小操作数。如题目中的示例最小操作数为4，不过这一题在poj上的测试数据比较水，

短命女/ 2022年08月11日 03:23/ 0 赞/ 27 阅读

相关 POJ Tautology

Tautology <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

た入场券/ 2022年07月10日 04:16/ 0 赞/ 198 阅读

相关 POJ 3356 AGTC（dp之公共最长子序列）

Let x and y be two strings over some finite alphabet A. We would like to transform xinto

偏执的太偏执、/ 2022年06月10日 23:08/ 0 赞/ 183 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 224 阅读

相关 poj1007

1．链接地址 [https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007] 2．问题描述

深藏阁楼爱情的钟/ 2021年11月23日 15:38/ 0 赞/ 255 阅读

相关 poj 1009

参考自大神思路：[POJ 1009][] 首先，暴力必挂，这是题目的善意提醒。于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的

刺骨的言语ヽ痛彻心扉/ 2021年11月02日 00:46/ 0 赞/ 265 阅读