El de la distancia de edición (I) P26005


Statement
 

pdf   zip

thehtml

Algunos problemas son tan clásicos que apenas merecen enunciado. En este, debéis calcular el coste mínimo de insertar letras en dos palabras p1 y p2 para hacerlas idénticas. Ambas palabras están compuestas por letras escogidas de entre las n primeras minúsculas (por ejemplo, para n=4, el alfabeto es {a, b, c, d}). Para cada letra (llamémosla x), insertar una x en cualquier lugar de cualquier palabra tiene coste Ix.

Entrada

La entrada consiste en diversos casos. Cada caso empieza con 2≤ n≤ 26, seguido de n ‍naturales estrictamente positivos Ia, Ib, Ic, …. Siguen dos palabras p1 y p2 con entre 1 y ‍1000 letras minúsculas elegidas entre las n primeras. Podéis asumir 1≤ Ix≤ 1000 para cada letra x.

Salida

Para cada caso, escribid el coste mínimo de conseguir que p1 y p2 sean idénticas.

Public test cases

  • Input

    2
11 10
aaa
aba

4
100 100 100 1
abcd
bcda

3
1 10 100
abbcabccabbac
bbcabacabbac

4
1 2 1 4
dcbbcbbddccdabdbdbdcbbc
cddcab

    Output

    21
200
102
40
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Python