pku 3356 AGTC

客官°小女子只卖身不卖艺 2022-08-13 17:40 2阅读 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 条评论，2人围观）

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

相关阅读

相关 pku 3176 水

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

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

相关 pku 3356 AGTC

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

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

相关 pku 1088 滑雪

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

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

相关 pku 1426 bfs

\include <iostream> using namespace std; \_\_int64 q\[1100000\]; int n; \_\_int64 bfs()

左手的ㄟ右手/ 2022年08月13日 12:38/ 0 赞/ 16 阅读

相关 pku 1101 bfs

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

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

相关 pku 1146 dfs

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

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

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

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

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

相关 pku 1456 Supermarket

\include <iostream> \include <cstdio> \include <algorithm> using namespace std; \define

深碍√TFBOYSˉ_/ 2022年07月12日 10:10/ 0 赞/ 152 阅读

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

相关 pku 1330 LCA

第一道LCA \include < stdio.h > \include < string .h > \define N 10001 int uni

柔光的暖阳◎/ 2021年11月01日 13:24/ 0 赞/ 277 阅读