🗊Презентация Олимпиадные задачи. Динамическое программирование

Олимпиадные задачи Динамическое программирование Григорьева А.В.

Задача «Возрастающая подпоследовательность»

Пример

Решение

Детали реализации

Сдать можно как задачу №613 http://informatics.mccme.ru/mod/statements/view3.php?chapterid=613#1

Задача «Таблица»

Первый способ

Второй способ С диагоналями. Нужен, чтобы хранить не 3 строки одной таблицы (B), а по две строки трех таблиц (L, R, B)

Задача «Черепашка»

Решение задачи «Черепашка». П.П. Полный перебор вариантов – универсальный способ решения. Но рассмотрим его потенциальные возможности Пусть дана таблица 4х4. Любой путь состоит из трёх перемещений вверх и трех перемещений вправо, т.е. длина пути равна шести. Другими словами, дано 6 шагов, из них 3 выбираются для перемещений вверх, оставшиеся 3 – для перемещений вправо определяются однозначно. Т.о. количество способов выбора трех перемещений из шести При нахождении суммы (стоимости) пути потребуется 5 операци сложения, всего 100 операций. Оценим время решения задачи для компьютера с миллионным быстродействием (см. презентация предыдущих занятий о сложности алгоритмов и быстродействии на примере задачи о тупоугольном треугольнике)

Длительность вычислений

Решение задачи «Черепашка». Д.П.

Код (на паскале)

Вычисление пути

Вычисление пути

Сдать можно как задачу №2965 Там даже не требуется вывести путь И идет черепашка в другом направлении http://informatics.mccme.ru/mod/statements/view3.php?id=656&chapterid=2965#1