El de la distancia de edición (II) P48188


Statement
 

pdf   zip

thehtml

A estas alturas, seguro que ya os suena lo de que algunos problemas son tan clásicos que bla, bla, bla. Nada nuevo: éste también lo es. Ahora, os pedimos que calculéis el coste mínimo de insertar letras o de modificar 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émosle x), insertar una ‍x en cualquier lugar de cualquier palabra tiene coste Ix. El coste de transformar una letra ‍x en una letra y viene dado por ⌈ (Ix+Iy)/4⌉, es decir, una cuarta parte, redondeando para arriba, de la suma de los costes de inserción Ix y Iy.

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

    6
    54
    27
    35
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++