2857. 编辑距离

cd106224
//状态 dp[i][j]表示a的前i位变成b的前j位所要的最少时间
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[502][502];

string a, b;
int main() {
    int n;
    cin >> n;
    while (n--) {
        fill(dp[0], dp[0] + 502 * 502, 0);
        for (int i = 0; i < 502; ++i) {
            dp[i][0] = i;
            dp[0][i] = i;
        }
        cin >> a >> b;
        for (int i = 1; i <= a.size(); ++i) {
            for (int j = 1; j <= b.size(); ++j) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        cout << dp[a.size()][b.size()] << endl;
    }
    return 0;
}
clysto
#include <bits/stdc++.h>

using namespace std;


int main() {
    int N;
    cin >> N;
    while (N--) {
        string A, B;
        int ld[501][501];
        cin >> A >> B;
        for (int i = 0; i <= A.length(); i++) {
            ld[0][i] = i;
        }
        for (int i = 0; i <= B.length(); i++) {
            ld[i][0] = i;
        }
        for (int x = 1; x <= B.length(); x++) {
            for (int y = 1; y <= A.length(); y++) {
                if (A[y - 1] == B[x - 1]) {
                    ld[x][y] = ld[x - 1][y - 1];
                } else {
                    ld[x][y] = min(ld[x - 1][y], min(ld[x][y - 1], ld[x - 1][y - 1])) + 1;
                }
            }
        }
        cout << ld[B.length()][A.length()] << endl;
    }
    return 0;
}
10205101536

include

include

include

int minIN3(int a,int b,int c){
int min = (a<b)?a:b;
return (min<c)?min:c;
}
int main(){
char * a = (char)malloc(sizeof(char)500);
char * b = (char)malloc(sizeof(char)500);
a[0] = ‘ ‘;//首字符置为空格,方便dp[0][0]初始化
b[0] = ‘ ‘;
int N;
scanf(“%d”,&N);
getchar();
for(int i =0;i<N;i++){
gets(a+1);
gets(b+1);
int aLen = strlen(a);
int bLen = strlen(b);
int edit[bLen][aLen];
for(int i = 0 ;i<aLen;i++){
edit[0][i] = i;
}
for(int j = 0 ;j<bLen;j++){
edit[j][0] = j;
}
int i ;
for( i =1;i<bLen;i++){
for(int k = 1;k<aLen;k++){
edit[i][k] = minIN3(edit[i-1][k]+1,edit[i][k-1]+1,edit[i-1][k-1]+((a[k]==b[i])?0:1));//状态转移方程
}
}
printf(“%d\n”,edit[bLen-1][aLen-1]);

}

}

NBC++

莱温斯坦距离

include

using namespace std ;

int num [501][501] ;
int main (){
int T ,i ;
cin >> T;
for (i =0;i > a >> b;
int lena = a.length () ;
int lenb = b.length () ;
int j,k ;
for (j =0;j <=lenb;j ++)
num [j][0] = j ;
for (k =0;k <=lena;k ++)
num [0][k] = k ;
for (j=1;j <=lenb;j ++){
for (k =1;k <=lena;k ++){
if (a[k-1] == b [j-1])
num [j][k] = num [j-1][k-1];
else {
int c = min (num[j-1][k],num[j][k-1]);
int d = min (c,num[j-1][k-1]) ;
num [j][k] = d +1;
}
}
}
cout << num [lenb][lena] << endl ;
}
}

HongRed

好久不做题, 状态转移方程推起来都很费劲.

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<utility>
#include<cassert>
#include<climits>
using namespace std;


int main()
{
#ifdef debug
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    int T;
    char str1[501], str2[501];
    scanf("%d", &T);
    unsigned editdistance[503];
    memset(editdistance, 0, sizeof(editdistance));
    while(T--)
    {
        scanf("%s%s", str1, str2);
        const unsigned size1 = strlen(str1);
        const unsigned size2 = strlen(str2);

        // When looking at the first char of str1.
        for(unsigned i = 1; i <= size2; i++)
            editdistance[i] = i;

        // Dynamic Programming
        for(unsigned i = 1; i <= size1; i++)
        {
            // Looking at the first char of str2
            editdistance[0] = i;
            unsigned ij = i - 1;
            for(unsigned j = 1; j <= size2; j++)
            {
                if(i - 1 < size1 && j - 1 < size2 && str1[i-1] != str2[j-1]) ij++;
                int a = min(min(editdistance[j-1], editdistance[j]) + 1, ij);
                ij = editdistance[j];
                editdistance[j] = a;
            }
        }
        printf("%u\n", editdistance[size2]);
    }
    return 0;
}
MasterKiller

此处Shut down MasterX 记录

10162100115

这题不是求最长公共序列么?

10175101189

不是最长公共序列好吧 有些位置还要先删掉再在其他位置上加 不是相等的关系

10175101121

比如abc修改成acb

DeadCrow

不对

你当前正在回复 博客/题目
存在问题!