pku 3356 AGTC

客官°小女子只卖身不卖艺 2022-08-13 17:40 29阅读 0赞

\#include <iostream> \#include <string> using namespace std; int v\[1001\]\[1001\]; int main() \{ int m, n; string s1, s2; while(scanf("%d", &m)!=EOF) \{ cin >> s1; scanf("%d", &n); cin >> s2; for(int i = 1; i <= n; ++i) v\[0\]\[i\] = i; for(int i = 1; i <= m; ++i) v\[i\]\[0\] = i; for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) if(s1\[i-1\] == s2\[j-1\]) v\[i\]\[j\] = min(min(v\[i-1\]\[j-1\], v\[i-1\]\[j\]+1), v\[i\]\[j-1\]+1); else v\[i\]\[j\] = min(min(v\[i-1\]\[j-1\]+1, v\[i-1\]\[j\]+1), v\[i\]\[j-1\]+1); printf("%d/n", v\[m\]\[n\]); \} return 0; \} /\* min\{v\[i-1\]\[j-1\], v\[i-1\]\[j\]+1, v\[i\]\[j-1\]+1\} (s\[i\] = s\[j\]) v\[i\]\[j\] = min\{v\[i-1\]\[j-1\]+1, v\[i-1\]\[j\]+1, v\[i\]\[j-1\]+1\} (s\[i\] != s\[j\]) //1.s\[i\] = s\[j\],其中v\[i-1\]\[j-1\]+1表示不作处理,v\[i-1\]\[j\]+1表示删除字符s\[i\], v\[i\]\[j-1\]+1表示在s\[i\]后添加s\[j\] //s\[i\] != s\[j\],其中v\[i-1\]\[j-1\]+1表示把s\[i\]变成s\[j\],v\[i-1\]\[j\]+1表示删除字符s\[i\], v\[i\]\[j-1\]+1表示在s\[i\]后添加s\[j\] //2.注意初始化的处理 result: Problem: 3356 User: xiaofengsheng Memory: 4288K Time: 32MS Language: G++ Result: Accepted \*/

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 25 阅读

相关 pku 3176 水

\include <iostream> \include <cstdio> \include <cstring> using namespace std; int map\[3

我不是女神ヾ/ 2022年08月14日 04:46/ 0 赞/ 174 阅读

相关 pku 3356 AGTC

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

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

相关 pku 1088 滑雪

\include <iostream> using namespace std; int map\[100\]\[100\]; int v\[100\]\[100\]; int

╰半夏微凉°/ 2022年08月13日 12:46/ 0 赞/ 205 阅读

相关 pku 1101 bfs

/\ //很很很经典的bfs, 这也是我第一次正式用bfs来刷题, 感受颇深: //one.cpp是用bfs来解决从一个点到另一个点的最短路程长度的方法(写的有点冗杂) 注意的

向右看齐/ 2022年08月13日 12:37/ 0 赞/ 192 阅读

相关 pku 1146 dfs

\include <iostream> using namespace std; \define MAX 52 int map\[MAX\]\[MAX\]; bool visi

我就是我/ 2022年08月13日 06:29/ 0 赞/ 211 阅读

相关 POJ——3356 ACGT

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

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

相关 AGTC(动态规划-最短编辑距离)

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

╰半橙微兮°/ 2022年08月02日 14:49/ 0 赞/ 244 阅读

相关 pku 3176

\include<stdio.h> int str\[351\]\[351\]; int main() \{ int n,i,j; // freopen("

小鱼儿/ 2022年06月17日 23:29/ 0 赞/ 169 阅读

相关 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 赞/ 174 阅读