Задача из раздела комбинаторика, но на мой взгляд - это в чистом виде динамическое программирование. Давайте разбираться:
Давайте посмотрим на последний ряд дерева. Понятно, что все листья разбиваются на группы по 2 или 3. Научимся считать количество разбиений методом динамического программирования.
База динамики: 2, 3 и 4 элемента разбиваются единственным способом.
Шаг динамики, если все ответы до i элементов посчитаны: какой могла быть последняя группа? Всё те же 2 или 3 элемента, то есть ответ для задачи размера i складывается из ответов для подзадач размера i - 2 и i - 3.
То есть решение будет почти как в Задача 147. Числа Фибоначчи, только шаги немного другие.
Однако в нашей задаче не всё так просто, потому что, зная количество разбиений для нижнего слоя дерева, нельзя посчитать количество разбиений предыдущего слоя, так как количество групп, на которые разбили элементы нижнего слоя может отличаться - значит и количество элементов на предыдущем слое тоже будет отличаться.
Это видно даже на примере из условия задачи. Да, нижний слой разбивается двумя способами. Но предыдущий уже может иметь как 2, так и 3 вершины. В этом случае неважно, так как они оба имеют лишь один вариант разбиения. Но в общем случае это не так.
Поэтому доработаем динамику и будем хранить не только количество элементов, но и количество групп, на которые они разбиваются. Тогда получается двумерная динамика. Пример заполненной таблицы:
Здесь строки - это количество разбиваемых элементов, столбцы - количество групп. Тогда при заполнении очередной строки i надо смотреть на строки i - 2 и i - 3. И столбец на единицу меньше, так как количество групп вырастает на один.
При ограничениях из условия задачи, такая таблица будет довольно большой: 5000х2500 (так как максимальное количество групп будет в два раза меньше). Но заметим, что каждый раз нам надо лишь четыре последние строки, вот их и будем хранить.
Как же из этой таблицы получить ответ на задачу? Никак, нам понадобится ещё один массив динамического программирования (res), в котором будем накапливать ответы для деревьев всех размеров.
И тогда уже можно получить ответ. Например для дерева размера 12 он будет состоять из трёх слагаемых:
- одним способом можно разбить элементы на четыре группы, а дерево размера 4 строится единственным образом, то есть 1 * 1
- десятью способами можно разбить элементы на пять групп, а дерево размера 5 тоже строится единственным образом, то есть 10 * 1
- одним способом можно разбить элементы на шесть групп, а дерево размера 6 строится двумя способами, то есть 1 * 2
Итоговое количество будет 13.
Как обычно, самое сложное в динамическом программировании - разобраться, потому что код будет совсем простой.
Заводим массив для ответов и четыре массива для хранения последних строк рассмотренной таблицы:
Всё можно сделать размера l, чтобы сильно много не думать. По факту, как мы выяснили, ширина таблицы не может быть больше l / 2.
А дальше переберём все размеры деревьев до l и будем параллельно вычислять строки таблицы и заполнять массив с ответами:
Здесь мы делаем циклический сдвиг четырёх массивов, а потом в цикле пересчитываем последний. Так в нём получаются данные очередной строки таблицы. И одновременно с этим, накапливаем ответ в res.
Стоит заметить, что это решение на Python всё-таки не укладывается в лимиты по времени (довольно много операций, среди которых времезатратное взятие остатка от деления), но залетает на PyPy.
Предыдущий выпуск: Задача 707. Zuma
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.