Разбор задачи F. Квадродерево

Тема: динамическое программирование
Сложность: высокая

Постановка задачи
Дано квадродерево на таблице из 0 и 1
Найти минимальное число вершин, которое может остаться, при изменении не более, чем `k` ячеек

Решение
Посчитаем динамику на полном квадродереве, то есть в каждой вершине посчитаем – какое минимальное количество ячеек нужно изменить, чтобы в квадродереве с корнем в этой вершине было ровно `m` вершин

Обоснование
Если таблица имеет размер `n*n` – то количество вершин в квадродереве `O(n^2)`
Каждая такая вершина "пересчитывается" за `O(n^4)`
`T(n)\ =\ O(n^4)\ +\ 4T(n/4)\ =\ O(n^4)`
Итого: `O(n^4)` – время работы программы

Автор разбора: Аксёнов Виталий, СПбГУ ИТМО