Re: задачка с acm.uva.es :)

From

Vladislav Gusev (2:5059/9.75)

To

Alexey Burdin

Date

2002-12-09T16:15:42Z

Area

RU.ALGORITHMS

                     Приветствую тебя Alexey !!!
 Было это [07 декабря 2002]. Alexey Burdin писал к All.

 AB>     Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
 AB>     Необходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
 AB>     в нем была максимальна (из всех возможных таких прямоугольников).

 AB>     На ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 , x1<=x2<=100,
 AB>     y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
 AB>     Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)
 AB>     Хотелось бы что-нибудь более оптимальное, но влезающее в досовые 400к
 AB> :),    желательно чтобы работало на "раз-два-три".
 А ширина\высота прямоугольника дана или нет ?
 вот такой велосипед  :
 Создать массив в nxn раз меньшего исходного ,то есть как бы разбить его на
"ячейки", для каждой "ячейки" посчитать, сумму элементов исходного массива,
содержащихся  в ней. Теперь найдя прямоугольник с максимальный суммой в таком
массиве, имхо можно утверждать, что в исходном массиве его координаты лежат в
районе: cell_x1 - cell_width < x1 < cell_x1 + cell_width,и т.д
дальше небольшим перебором, можно разбиение ещё иерархическим сделать...

                                                С уважением Vlad.

--- GoldED+/386 1.1.4.5
 * Origin: End Of All Hope (2:5059/9.75)