Ну там вроде предпологалось написать динамику + meet in the middle за что-то вроде O(n * 2^(n /2)). Как это сделать честно за 0.062 правда не особо понятно.
2 2009-11-06 17:56:10
Re: Подматрица с максимальной суммой (4 ответов, оставленных в Algo)
1717 решается например так:
Посортить вершины по x, перебрать левую границу прямоугольника x1, внутри завести дерево отрезков по y, где в каждой вершине для подотрезка хранить: сумму функций на отрезке, сумму на лучшем подотрезке, сумму лучшего подотрезка начинающегося в левой границе и заканчивающегося раньше правой, сумму лучшего подотрезка начинающегося раньше правой границы и заканчивающегося в ней, последнее 2 отдельно для 1 и >= 2 команд. После того как выбрали левую границу и завели дерево надо по очереди делать следующее: прорелаксировать все вершины с первым нерассмотренным x >= x1, узнать ответ (лучший подотрезок корня для >= 2 команд).
3 2009-10-16 00:52:55
Re: Динамика по профилю. Задача "паркет" (13 ответов, оставленных в Algo)
Можно про последний поподробнее?