Editorial for BLAST


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=2001;
var n,m,k:longint;
    f:array[0..maxn,0..maxn] of longint;
    a,b:array[1..maxn] of char;
    s:array['a'..'z','a'..'z'] of longint;

procedure rf;
var i:longint; p,q:char;
begin
     assign(input,fi);
     reset(input);
     m:=0;
     while not eoln do
     begin
          inc(m);
          read(a[m]);
     end;
     readln;
     n:=0;
     while not eoln do
     begin
          inc(n);
          read(b[n]);
     end;
     readln;
     read(k);
     for p:='a' to 'z' do
         for q:='a' to 'z' do
             s[p,q]:=abs(ord(p)-ord(q));
     close(input);
end;

function min(a,b,c:longint):longint;
begin
     if (a<b) and (a<c) then min:=a
     else
     begin
          if b<c then min:=b else min:=c;
     end;
end;

procedure pr;
var i,j:longint;
begin
     for i:=0 to n do f[0,i]:=i*k;
     for i:=0 to m do f[i,0]:=i*k;
     for i:=1 to m do
      for j:=1 to n do
       f[i,j]:=min(f[i-1,j-1]+s[a[i],b[j]],f[i-1,j]+k,f[i,j-1]+k);
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(f[m,n]);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 2000+5;
char s[N], t[N];
int k, f[N][N];

int main() {
    scanf("%s%s%d",s+1,t+1,&k);
    int n = strlen(s+1), m = strlen(t+1);
    for(int i = 1; i <= n; ++i) f[i][0] = k * i;
    for(int j = 1; j <= m; ++j) f[0][j] = k * j;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            f[i][j] = min(abs(s[i] - t[j]) + f[i-1][j-1], k + min(f[i][j-1], f[i-1][j]));
    printf("%d\n", f[n][m]);
    return 0;
}

Code mẫu của ladpro98

program mblast;
uses    math;
const   fi='';
        maxN=2345;
var     f:array[0..maxN,0..maxN] of longint;
        a,b:ansistring;
        k:longint;

procedure input;
var     inp:text;
        t:ansistring;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,a);
        readln(inp,b);
        readln(inp,k);
        close(inp);
end;

procedure dp;
var     i,j:longint;
begin
        f[0,0]:=0;
        for i:=0 to length(a) do
        for j:=0 to length(b) do
        begin
                if (i=0) and (j=0) then continue;
                if i=0 then f[i,j]:=f[i,j-1]+k
                else
                if j=0 then f[i,j]:=f[i-1,j]+k
                else
                f[i,j]:=min(min(f[i-1,j]+k,f[i,j-1]+k),f[i-1,j-1]+abs(ord(a[i])-ord(b[j])));
        end;
end;

begin
        input;
        dp;
        write(f[length(a),length(b)]);
end.

Code mẫu của RR

//Written by RR
  {$R+,Q+}
  {$Mode objFPC}
uses math;
const
  FINP          =       {$IFDEF RR} 'input.txt';  {$ELSE} ''; {$ENDIF}
  FOUT          =       {$IFDEF RR} 'output.txt'; {$ELSE} ''; {$ENDIF}
  MAXN          =       2222;
var
  f1,f2         :       text;
  a,b           :       ansistring;
  f             :       array[0..MAXN,0..MAXN] of longint;
  m,n,cost      :       longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    begin
      readln(f1,a); m:=length(a);
      readln(f1,b); n:=length(b);
      readln(f1,cost);
    end;
procedure solve;
    var
      i,j:longint;
    begin
      for i:=1 to m do
        f[i,0]:=cost*i;
      for i:=1 to n do
        f[0,i]:=cost*i;
      for i:=1 to m do
        for j:=1 to n do
          f[i,j]:=min(f[i-1,j-1]+abs(ord(a[i])-ord(b[j])),
                      min(f[i-1,j],f[i,j-1])+cost);

      writeln(f2,f[m,n]);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#include <cstring>

using namespace std;

int s[2020][2020];
char s1[2020],s2[2020];
int blank;

int TTD(int x) { return x>0 ? x: -x;}

int main()
{
    int s1len,s2len,i,j;
    scanf("%s %s %d",s1,s2,&blank); 
    s1len = strlen(s1);
    s2len = strlen(s2);
    s[0][0] = 0;
    for(j = 1;j<= s2len; j++) s[0][j] = s[0][j-1] + blank;
    for(i = 1;i<= s1len; i++)
    {
          s[i][0] = s[i-1][0] + blank;
          for(j = 1;j<=s2len;j++)
          {
                s[i][j] = s[i-1][j-1]+TTD(s1[i-1]-s2[j-1]);
                if(s[i-1][j]+blank<s[i][j]) s[i][j] = s[i-1][j]+blank;
                if(s[i][j-1]+blank<s[i][j]) s[i][j] = s[i][j-1]+blank ;
          }
    }
    printf("%d\n",s[s1len][s2len]);
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MBLAST;
  Const
    input  = '';
    output = '';
    maxn = 2000;
  Var
    a,b: string;
    la,lb: integer;
    F: array[0..maxn,0..maxn] of integer;
    k: integer;

Procedure init;
  Var
    fi: text;
  Begin
    Assign(fi, input);
      Reset(fi);

    Readln(fi, a);
    la:= length(a);

    Readln(fi, b);
    lb:= length(b);

    Readln(fi, k);

    Close(fi);
  End;

Procedure optimize;
  Var
    i,j,t: integer;
  Begin
    For i:= 0 to la do F[i,0]:= i * k;
    For i:= 0 to lb do F[0,i]:= i * k;

    For i:= 1 to la do
      For j:= 1 to lb do
        Begin
          F[i,j]:= F[i,j - 1] + k;

          t:= F[i - 1,j] + k;
          If F[i,j] > t then F[i,j]:= t;

          t:= F[i - 1,j - 1] + abs(ord(a[i]) - ord(b[j]));
          IF F[i,j] > t then F[i,j]:= t;
        End;
  End;

Procedure printresult;
  Var
   fo: text;
  Begin
    Assign(fo, output);
      Rewrite(fo);
      Writeln(fo, F[la,lb]);
    Close(fo);
  End;

Begin
  init;
  optimize;
  printresult;
End.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.