Динамическое программирование по подстрокам

2 задачи
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Наименьшая сумма ASCII кодов#47638

Вам даны две строки s1 и s2. Вы можете удалить из обоих строк любое количество символов. Ваша цель сделать строки одинаковыми.
Найдите наименьшую сумму ASCII кодов всех удаленных символов.


Входные данные
Программа получает на вход две строки s1 и s2.

Ограничения

  • 1 <= длина s1 и s2 <= 1000;
  • s1 и s2 состоят из маленьких английских букв.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
sea
eat
 
231
 Удаление "s" из слова "sea" добавляет к сумме ASCII код буквы "s" (115).
Удаление буквы "t" из слова "eat" добавляет к сумме 116.
В итоге обе строки равны, а 115 + 116 = 231 - минимально возможная сумма для достижения этой цели.
Динамическое программирование по подстрокам
✓ 11✗ 161 000средняяВойти и решать
Восстановление скобок#23412
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
 
Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
 
Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109.
 
 
Примеры
№ Входные данные Выходные данные
1 ????(? 2
 
Динамическое программирование по подстрокамДинамическое программирование: два параметра
✓ 116✗ 190800средняяВойти и решать
Поделиться
Класснуть