|
|
|
|
|
|
|
Вернуться
| 1 Меньшиков Фёдор Владимирович, 17 сентября 2018 г. 17:47:20 | |
|
В архиве acmp задач на ДП очень много, более сотни. Для многих из них можно найти разборы.
|
|
|
| 2 Меньшиков Фёдор Владимирович, 17 сентября 2018 г. 17:44:31 | |
|
Номер задачи "Марсианский язык" - 1593. Это стандартная задача на динамическое программирование. Будем отвечать на вопрос задачи (максимальное качество строки) для каждого префикса исходной строки. Переход - перебираем длину последнего слова от L до R, без него получается меньший префикс, для которого ответ уже известен. Добавляем к нему качество последнего слова. Качество последнего слова зависит только от минимальной и максимальной буквы, поэтому можно не получать его заново для каждой длины, а обновлять эту информацию за O(1) при увеличении длины слова на 1. Восстановление ответа тоже стандартное - в момент принятия решения о бОльшей сумме запоминаем, какой длины было последнее слово. Потом идём с конца, каждый раз убирая последнее слово.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
