/ Vijos / 题库 / 距离 /

题解

62 条题解

  • 1
    @ 2017-05-25 13:27:01
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    const int maxn = 2010;
    int dp[maxn][maxn];
    
    int main() {
        ios::sync_with_stdio(false);
        string s1, s2;
        int k;
        while (cin >> s1 >> s2 >> k) {
            int n = s1.length(), m = s2.length();
            for (int i = 1; i <= n; i++)
                dp[i][0] = i * k;
            for (int i = 1; i <= m; i++)
                dp[0][i] = i * k;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) + k, dp[i - 1][j - 1] + (int)abs(s1[i - 1] - s2[j - 1]));
            cout << dp[n][m] << endl;
        }
        return 0;
    }
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    const int maxn = 2010;
    int dp[maxn][maxn];
    
    int main() {
        ios::sync_with_stdio(false);
        string s1, s2;
        int k;
        while (cin >> s1 >> s2 >> k) {
            int n = s1.length(), m = s2.length();
            for (int i = 1; i <= n; i++)
                dp[i][0] = i * k;
            for (int i = 1; i <= m; i++)
                dp[0][i] = i * k;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) + k, dp[i - 1][j - 1] + (int)abs(s1[i - 1] - s2[j - 1]));
            cout << dp[n][m] << endl;
        }
        return 0;
    }
    
  • 1
    @ 2016-11-17 21:10:14

    测试数据 #0: Accepted, time = 0 ms, mem = 16340 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 16344 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 16340 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 16340 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 16344 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 16344 KiB, score = 10

    测试数据 #6: Accepted, time = 15 ms, mem = 16340 KiB, score = 10

    测试数据 #7: Accepted, time = 15 ms, mem = 16340 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 16340 KiB, score = 10

    测试数据 #9: Accepted, time = 31 ms, mem = 16340 KiB, score = 10

    Accepted, time = 76 ms, mem = 16344 KiB, score = 100
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    using namespace std;
    #define rep(i,n) for(int i=1;i<=n;i++)
    const int maxn=2000+7;
    int f[maxn][maxn],a[maxn],b[maxn],k,lena,lenb;
    char al[maxn],bl[maxn];
    int main()
    {
    // freopen("in.txt","r",stdin);
    scanf("%s",al);
    scanf("%s",bl);
    lena=strlen(al);lenb=strlen(bl);
    scanf("%d",&k);
    rep(i,lena)a[i]=al[i-1];
    rep(i,lenb)b[i]=bl[i-1];
    f[0][0]=0;
    rep(i,lena)f[i][0]=f[i-1][0]+k;
    rep(i,lenb)f[0][i]=f[0][i-1]+k;
    rep(i,lena)
    rep(j,lenb)
    f[i][j]=min(f[i-1][j-1]+abs(a[i]-b[j]),min(f[i-1][j],f[i][j-1])+k);
    printf("%d",f[lena][lenb]);
    return 0;
    }

  • 0
    @ 2021-03-14 12:33:09
    不不不
    
  • 0
    @ 2016-08-16 11:13:59
  • 0
    @ 2016-05-06 21:00:19

    AC99纪念
    测试数据 #0: Accepted, time = 15 ms, mem = 16544 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 16544 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 16580 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 16652 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 17108 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 16804 KiB, score = 10
    测试数据 #6: Accepted, time = 62 ms, mem = 16828 KiB, score = 10
    测试数据 #7: Accepted, time = 62 ms, mem = 16824 KiB, score = 10
    测试数据 #8: Accepted, time = 93 ms, mem = 16832 KiB, score = 10
    测试数据 #9: Accepted, time = 125 ms, mem = 16856 KiB, score = 10
    Accepted, time = 418 ms, mem = 17108 KiB, score = 100
    ------------------------------华丽的分割线------------------------------
    ```pascal
    type int=longint;
    var
    s1,s2:ansistring;
    l1,l2,k:int;
    a:array[0..2000,0..2000]of int;
    function min(x,y,z:int):int;
    begin
    min:=x;
    if y<min then min:=y;
    if z<min then min:=z;
    exit(min);
    end;

    function f(x,y:int):int;
    begin
    if a[x,y]>0 then exit(a[x,y]);
    if (x=0)or(y=0) then exit((x+y)*k);
    f:=min(f(x-1,y-1)+abs(ord(s1[x])-ord(s2[y])),f(x-1,y)+k,f(x,y-1)+k);
    a[x,y]:=f;
    end;

    begin
    readln(s1);
    readln(s2);
    readln(k);
    l1:=length(s1);
    l2:=length(s2);
    fillchar(a,sizeof(a),0);
    writeln(f(l1,l2));
    end.
    ```
    我在**秋名山**等你!!!

  • 0
    @ 2016-03-16 20:41:59

    var
    s1,s2:ansistring;
    a:array [0..2100,0..2100] of longint;
    k,l1,l2,i,j:longint;
    function min(x,y:longint):longint;
    begin if (x<y) then exit(x) else exit(y); end;
    begin
    readln(s1);
    readln(s2);
    read(k);
    l1:=length(s1);
    l2:=length(s2);
    fillchar(a,sizeof(a),10);
    for i:=0 to l1 do a[i,0]:=i*k;
    for i:=0 to l2 do a[0,i]:=i*k;
    for i:=1 to l1 do
    for j:=0 to l2 do
    a[i,j]:=min(a[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])),min(a[i-1,j]+k,a[i,j-1]+k));
    writeln(a[l1,l2]);
    end.

  • 0
    @ 2015-07-15 21:09:45

    预处理好纠结

  • 0
    @ 2015-07-11 10:42:49

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<cstdlib>
    using namespace std;

    char c[3000],d[3000];
    char a[3000],b[3000];
    int f[2100][2100];

    int main()
    {
    cin>>c>>d;
    int k;
    cin>>k;
    int lena=strlen(c);
    int lenb=strlen(d);
    for(int i=1; i<=lena; i++)
    a[i]=c[i-1];
    for(int i=1; i<=lenb; i++)
    b[i]=d[i-1];
    for(int i=1; i<=lena; i++)
    f[i][0]=f[i-1][0]+k;
    for(int j=1; j<=lenb; j++)
    f[0][j]=f[0][j-1]+k;
    for(int i=1; i<=lena; i++)
    for(int j=1; j<=lenb; j++)
    f[i][j] = min(f[i-1][j-1]+abs(a[i]-b[j]),min(f[i-1][j],f[i][j-1])+k);

    cout<<f[lena][lenb];
    return 0;
    }

  • 0
    @ 2015-05-20 15:34:23

    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    char a[2005],b[2005];
    int f[2005][2005];
    int lena,lenb,k;
    void Init(){
    char ch;
    lena=lenb=0;
    while(scanf("%c",&ch)&&(ch<='z')&&(ch>='a'))
    a[++lena]=ch;
    while(scanf("%c",&ch)&&(ch<='z')&&(ch>='a'))
    b[++lenb]=ch;
    scanf("%d",&k);
    }
    int main(){
    //freopen("p1.in","r",stdin);
    Init();
    for(int i=1;i<=lena;i++)
    f[i][0]=f[i-1][0]+k;
    for(int i=1;i<=lenb;i++)
    f[0][i]=f[0][i-1]+k;
    for(int i=1;i<=lena;i++)
    for(int j=1;j<=lenb;j++)
    f[i][j]=min(f[i-1][j-1]+abs(a[i]-b[j]),min(f[i-1][j],f[i][j-1])+k);
    printf("%d",f[lena][lenb]);
    return 0;
    }

  • 0
    @ 2014-10-29 21:44:53

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 16336 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 16344 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 16340 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 16336 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 16340 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 16344 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 16340 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 16340 KiB, score = 10
    测试数据 #8: Accepted, time = 46 ms, mem = 16344 KiB, score = 10
    测试数据 #9: Accepted, time = 46 ms, mem = 16340 KiB, score = 10
    Accepted, time = 214 ms, mem = 16344 KiB, score = 100
    代码
    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    #define M 2000+10

    using namespace std;

    int dp[M][M],sl,ssl,k;
    char s[M],ss[M];

    int main() {
    scanf("%s",s);scanf("%s",ss);scanf("%d",&k);
    sl = strlen(s);ssl = strlen(ss);
    memset(dp,0,sizeof(dp));
    dp[0][0]=0;
    for(int i = 1; i <=sl; i++) dp[i][0] = dp[i-1][0]+k;
    for(int i = 1; i <=ssl; i++) dp[0][i] = dp[0][i-1]+k;
    for(int i = 1; i <= sl; i++) {
    for(int j = 1; j <= ssl; j++) {
    dp[i][j] = dp[i-1][j-1] + abs(s[i-1]-ss[j-1]);
    dp[i][j] = min(dp[i][j],min(dp[i-1][j]+k,dp[i][j-1]+k));
    }
    }
    printf("%d",dp[sl][ssl]);
    return 0;
    }

  • 0
    @ 2014-08-14 23:44:28

    program p1680;
    var s1,s2:ansistring;
    i,j,k:longint;
    f:array[0..2000,0..2000] of longint;
    //
    function min(a,b,c:longint):longint;
    begin
    min:=10000;
    if a<min then min:=a;
    if b<min then min:=b;
    if c<min then min:=c;
    end;
    //
    begin
    readln(s1);
    readln(s2);
    readln(k);
    for i:=1 to length(s2) do f[0,i]:=i*k;
    for i:=1 to length(s1) do f[i,0]:=i*k;
    for i:=1 to length(s1) do
    for j:=1 to length(s2) do
    f[i,j]:=min(f[i,j-1]+k,f[i-1,j]+k,f[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])));
    write(f[i,j]);
    end.

  • 0
    @ 2014-03-29 11:06:42

    var s1,s2:ansistring;
    l1,l2,i,j,k:longint;
    f:array[0..2001,0..2001] of int64;
    function min(x,y,z:int64):int64;
    begin
    min:=x;
    if y<min then min:=y;
    if z<min then min:=z;
    end;
    begin
    readln(s1);l1:=length(s1);
    readln(s2);l2:=length(s2);
    readln(k);
    f[0,0]:=0;
    for i:=1 to l1 do f[i,0]:=f[i-1,0]+k;
    for i:=1 to l2 do f[0,i]:=f[0,i-1]+k;
    for i:=1 to l1 do
    for j:=1 to l2 do
    f[i,j]:=min(f[i-1,j]+k,f[i,j-1]+k,f[i-1,j-1]+abs(ord(s1[i])-ord(s2[j])));
    writeln(f[l1,l2]);
    end.
    怎么才能秒杀!orz大神!

  • 0
    @ 2013-11-02 21:54:21

    不知道为什么楼下的人都说这题很水,虽然我也一边AC,但至少我也思考了好一会才意识到的。
    一看题目就知道是DP。但刚开始方程没有往LCS这边想,而是往1264那题类似的方程想,导致花了一段无用功。。
    经过单步调试以后,发现了错误。才想到了LCS,方程也非常简单:
    f[i,j]:=min(f[i-1,j-1]+num,//i,j这两个数选取
    f[i-1,j]+k
    f[i,j-1]+k //用空格。

    剩下就是要处理边界,比较适合练手。

    DXE—SYF

  • 0
    @ 2010-03-11 17:32:07

    【分析】本题是一道典型的线性动归。

    首先考虑阶段的划分,A、B两串前面连续多少个字符是具备明显后效性的,也就是说取A的前i个和B的前j个所计算出来的最优值与后面如果引用此结构怎么放是没有影响的,所以用A的前I个和B的前J个连续字符来划分阶段是正确的,因为两串长度都不超2000,2000^2不会超时。

    下面来考虑情况:f要么把a[i]配到一起b[j],则有f+a[i]和b[j]间的距离,如果不配到一起,就把a[i]或b[j]中的一个单独处理加k值。

    【方程】F=Min{f+abs(ord(a[i])-ord(b[j])),f+k,f+k}

    参考程序见我的博客http://zhurui250.blog.163.com/blog/static/137270520201021152918767/edit/

  • 0
    @ 2009-11-10 20:25:53

    var

    a:array[0..2000,0..2000] of integer;

    i,j,k,g1,g2:integer;

    s1,s2:string;

    function f(n1,n2,n3:integer):integer;

    begin

    if n1>n2

    then f:=n2

    else f:=n1;

    if n1>n3

    then f:=n3;

    end;

    begin

    readln(s1);

    readln(s2);

    readln(k);

    g1:=length(s1);

    g2:=length(s2);

    for i:=1 to g1 do

    a:=i*k;

    for j:=1 to g2 do

    a[0,j]:=j*k;

    for i:=1 to g1 do

    for j:=1 to g2 do

    a:=f(a+abs(ord(s1[i])-ord(s2[j])),a+k,a+k);

    writeln(a);

    readln;

    end.

    哪里错了啊

    !!!!!!!!

  • 0
    @ 2009-11-03 23:02:02

    用f表示A的前i位和B的前j位进行比较时,所取得的最小值。

    则有f=min{f+k , f+k , f+abs(ord(A[i])-ord(B[j]))}

  • 0
    @ 2009-11-03 20:52:05

    program p1680;

    var a,b:string;k,i,j,n1,n2:integer;

    f:array[0..2003,0..2003] of integer;

    begin

    readln(input,a);

    readln(input,b);

    readln(input,k);

    n1:=length(a); n2:=length(b);

    for i:= 1to n1 do f:=k+f;

    for j:= 1to n2 do f[0,j]:=f[0,j-1]+k;

    for i:= 1to n1 do

    for j:= 1 to n2 do

    begin

    f:=f+abs(ord(a[i])-ord(b[j]));

    if f>f+k then f:=f+k;

    if f>f+k then f:=f+k;

    end;

    write(f[n1,n2]);

    end.

    哪错了? 怎么才40?

  • 0
    @ 2009-11-02 22:55:54

    三次才AC....我有罪..

    问大家两个问题...

    为什么一开始要吧F,F[0,J]都处理好?只处理F[0,1],F[1,0]不可以吗?

    还有,为什么一开始全赋0...不是应该赋正无穷吗?

  • 0
    @ 2009-10-31 22:55:15

    399+1同学,注意ansistring

  • 0
    @ 2009-10-31 18:57:14

    第一次把范围搞错了

信息

ID
1680
难度
3
分类
动态规划 | 动态规划 | LCS 点击显示
标签
(无)
递交数
1610
已通过
787
通过率
49%
被复制
3
上传者