НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ
Състезание_2
INF295
20.01.2004
Задача 4. Сравнение на символни низове
Дадени са два символни низа s1 и s2.
Задачата е от първия низ s1 да се получи втория низ s2,
като се използват операциите:
- insert(i,x) - вмъква символа x
на позиция i в s1;
- delete(i) - изтрива i-тия
символ на s1.
Индексът i се смята по първия низ.
За всяка от двете операции е зададена цена - за insert
цената е 2, а за delete - 3. Търсим крайна редица от операции
за решаване на задачата, която е с минимална цена. Напишете програма coms.exe,
която решава задачата и отпечатва намерената минимална цена.
ВХОД - файл coms.inp
Файлът съдържа броя на примерите и по два
низа на два реда за всеки пример. Низовете не са по-дълъги от 500 байта..
ИЗХОД - файл coms.out
За всеки пример да се отпечати намерената минимална
цена.
Пример.
2
abra
mabr
abc
xyz
|
Решение на примера.
5
15
|