1679
правок
Изменения
м
Нет описания правки
== Алгоритм ==
Алгоритм нахождения оптимального префиксного кода с сохранением порядка.
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.
Тогда пересчет <tex> D[i][j] </tex> будет происходить так:
<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + \sum\limits_{t = i}^{j} f_t </tex>
Добавочный член <tex> \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i - .. c_j </tex> также увеличиваются на 1.
Тогда такое k, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> [i, j]</tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> [i, j]</tex>.
== Монотонность точки разреза ==
