Автор: | М. Спорышев | Ограничение времени: | 10 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 1024 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 1 |
Вам даны:
Числа D, E — штрафы за начало нового разрыва в выравнивании строк и штраф за его продолжение соответственно.
Алфавит символов в виде строки A, состоящей из заглавных латинских букв.
Матрица замен символов R, соответствующая стоимости сопоставления каждой пары символов при выравнивании строк. Строки и столбцы матрицы соответствуют символам алфавита в том порядке, в котором они указаны в строке A
Две строки P и Q.
Требуется найти выравнивание строк P и Q, максимизирующее функцию стоимости данного выравнивания.
Выравнивание двух строк это также пара строк (Q1, Q2) одинаковой длины L, состоящих из символов алфавита, и символа "-", означающего разрыв.
Стоимость выравнивания S вычисляется по формуле: S(Q1, Q2) = ∑L − 1i = 0f(Q1[i], Q2[i]),
где f(Q1[i], Q2[i]) = D, если выполнено хотя бы одно из условий
f(Q1[i], Q2[i]) = E, если выполнено хотя бы одно из условий
Иначе f(Q1[i], Q2[i]) = R[Q1[i]][Q2[i]]
Первая строка содержит целые числа D, E.
Вторая строка содержит строку-алфавит A.
Далее |A| строк содержат по |A| целых чисел — элементы матрицы R.
Последние две строки содержат строки P и Q.
В первой строке выходного файла выведите стоимость выравнивания.
В последующих двух строках выведите выравнивание.
Если оптимальных решений несколько, выведите любое из них.
|D, E| ≤ 1000
− 10 ≤ Rij ≤ 10
Длина строк не превосходит 500. Строки состоят только из символов алфавита и не могут быть пустыми.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|