pku 3356 AGTC

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

#include #include 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 条评论，114人围观）

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

相关阅读

    相关 pku 1101 bfs

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

    向右看齐向右看齐/ 0 赞/ 286 阅读

    相关 POJ——3356 ACGT

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

    短命女短命女/ 0 赞/ 104 阅读