Кошки и выпуклые фигуры
В воскресном раунде на codeforces.ru была такая задача - http://codeforces.ru/contest/311/problem/B
Несмотря на заковыристое описание, сводится она к следующему:
- Дана последовательность S из m чисел в неубывающем порядке.
- Требуется разбить последовательность на p непрерывных групп [Pis, Pie] с минимизацией суммы sum{i=0,p-1}(sum{j=P[i].s,P[i].e-1}(S[P[i].e]-S[j]))
Обычное DP-решение дало сложность O(p*m^2) и не уложилось в отведенное время. Изучение вопроса показало, что есть интересный метод оптимизации такого рода проблем основанный в конечном счете на оптимизации запроса минимального значения семейства линейных функций (только порядка 1?) для заданной точки X. Подробности здесь. На досуге надо переписать решение, ибо техника выглядит good to know. В комментариях народ говорит, что это не техника, а очевидная хрень для любого, кто делал sweep line segment intersection, но я его никогда лично не делал, так что для меня это техника :)
UPDATE: Поправил формулу, и вот еще проясняющий пример. Дана неубывающая последовательность (3,5,6,6,7,8,10,11). Требуется разбить на три группы с минимизацией суммы по формуле выше. Графически это соответствует заштрихованной области на рисунке. Разбиение приведено произвольное - я не думал сейчас, оптимальное ли оно для этого конкретного примера.
