Теория: Лекция [Все занятия]
Практика: [Официальная страница]
Учебные задачи:
Задача A.
[Взрывоопасность]
Очевидно, если N = 1, то возможны два варианта: “А” и “B”. Если N = 2, то можно получить сразу две последовательность, заканчивающиеся на ‘B’, приписав ее к каждой последовательности, получившейся на предыдущем шаге, т.е. последовательности “AB” и “BB”. ‘A’ можно приписать только к одной последовательности “B”, получив “BA”. Итого, для N = 2 получили 3 варианта. Обозначим dp[i] – количество вариантов, которые можно получить из i-блоков. Продолжая рассуждения в той же духе можно заметить, что для любого i можно получить dp[i-1] последовательностей, приписав к ним блок ‘B’, а также dp[i-2] последовательностей, которые заканчиваются на ‘B’, к которым можно приписать блок ‘A’. В итоге получаем рекуррентную формулу dp[i] = dp[i-1] + dp[i-2]. Что является формулой вычисления числе Фибоначчи.
В классическом виде данная задача формулируется так: сколькими способами можно записать последовательность длины N из 0 и 1 без двух подряд идущих нулей.
Задача B.
[Наибольшая возрастающая подпоследовательность (НВП)]
Данную задачу мы уже решали несколько раз [1C из курса Меньшикова]. Но всегда полезно повторить изученное. В данном решении я привел квадратичное решение. С более быстрым решением можно ознакомится в разборе задачи 1C.
Задача C.
[0-1 Рюкзак]
Классическая задача на ДП, которую нужно уметь решать. На каждом шаге пытаемся набрать вес(j+w[i]), который формируется из веса гарантировано набранного на предыдущих шагах(j) + веса текущей вещи(w[i]). Стоимость такой новой комбинации формируется из стоимости вещей, набранных на предыдущем шаге(dp[j]) + стоимость текущей вещи(p[i]). Если получается так, что новая стоимость для веса j+w[i] более предпочтительна, т.е. превышает стоимость, полученную для этого веса на предыдущих шагах, то нужно обновить ее с учетом i-ой вещи. Суть сказанного иллюстрирует эта строка:
dp[j+ w[i]] = max(dp[j+ w[i]], dp[j] + p[i]);
Отметим тот факт, что изначально весь массив dp заполнен –1, а dp[0] = 0.
Олимпиадные задачи:
Задача A.
[Покупка билетов]
На каждом этапе пытаемся получить оптимальный ответ для первых N человек. Возможно лучшим решением было бы завести первые три барьерных элемента, но я ручками подсчитал первые три решения для n = 0,1 и 2, а дальше запустил цикл с рекуррентной формулой.
Задача B.
[Две стены]
Сразу сделаем важную оговорку. Необходимо использовать все кирпичи в наборе. Поэтому если вдруг получилось так, что сумма длин всех кирпичей цвета A не равна сумме длин кирпичей цвета B, значит построить две прямоугольные стены уже не получится. Будем использовать подход, который использовали в решении задачи о рюкзаке. А именно будем искать все возможные комбинации длин, которые можно получить из кирпичей одного цвета. Пусть SUM – сумма длин всех кирпичей одного цвета. Тогда необходимо найти такое значение SEP, что для каждого цвета можно набрать длину SEP и SUM-SEP. Если это сделать удалось, значит решение найдено.
Задача C.
[Репортаж]
Задача легко решается, что мы умеем решать задачу B из предыдущего блока, где нужно находить наибольшую возрастающую подпоследовательность(LIS). Для начала найдем LIS для исходного массива, а потом проделаем тоже самое только LIS будем искать не слева направо, а справа налево. В итоге останется только найти такую позицию в исходном массиве, для которой минимальное значение меньших элементов справа и слева будет максимально.
Дополнительные олимпиадные задачи:
Задача A.
[Отчет]
Задача сводится к поиску максимальной подпоследовательности, в которой возрастает общий объем производства и убывает процент бракованных изделий. Суть решения мало чем отличается от поиска LIS.
Задача B.
[Словарь]
Для каждой позиции i в тексте будем искать слово, на которое оно может оканчиваться. Для этого можно перебрать все слова(ограничения позволяют) из словаря и проверить можно ли сформировать текст, заканчивающийся позицией i – size, где size – длина текущего слова.
Задача C.
[Валютные махинации]
Несложная задача. Ее можно было дать и в учебных задачах, потому как она позволяет прочувствовать суть ДП на простом примере. Для каждого дня будем искать максимальное количество рублей, долларов и евро, которое можно получить за первые дни, оканчивающихся текущим. Максимальное количество рублей для текущего дня будет равно максимальному из значений:
1) Максимальное количество рублей с предыдущего дня
2) Максимальное количество долларов с предыдущего дня, переведенное по сегодняшнему курсу в рубли.
3) Максимальное количество евро с предыдущего дня, переведенное по сегодняшнему курсу в рубли.
Доллары и евро ищутся по схожей схеме.
