Изменения

печальная статья.__TOC__== Определение =={{Определение: | definition =[[Оптимальный префиксный код]] с сохранением порядка(англ. ''order-preserving code'', ''alphabetic code''). Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка, еслисоблюдаются:# Условие порядка - <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j</tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.# Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где <tex> f_i </tex> - количество(или вероятность) встретить символ <tex> c_i </tex> в тексте, а <tex>|p_i| </tex> - длина его кода.}}

Решим задачу , используя ДП на подотрезках. Пусть в ячейке D[i][j] хранится минимальная стоимость кодового дерева(???) для отрезка алфавита от i до j.Определение точки разреза:RТогда пересчет D[i][j]будет происходить так:Пересчет:<tex> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + S \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, на котором достигается этот минимум, называется точкой разреза для отрезка [i, j]. Пусть в ячейке R[i][j] хранится точка разреза на отрезке [i, j]. == Монотонность точки разреза =={{Теорема| about=Монотонность точки разреза| statement=<tex> R[i][j - 1] \leq R[i][j] \leq R[i + 1][j] </tex>| proof=????}}