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

From

Sasha Pelepeichenko (2:461/214.25)

To

Alexey Burdin

Date

2002-12-08T23:50:39Z

Area

RU.ALGORITHMS

                         Пpивет, _Alexey_!

07 Dec 02 Alexey Burdin write to All about "задачка с acm.uva.es :)":
 AB>     Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
 AB>     Необходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
 AB>     в нем была максимальна (из всех возможных таких прямоугольников).

 AB>     На ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 ,
 AB> x1<=x2<=100, y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
 AB>     Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)

можно зафиксиpовать x1 и двигать x2 до максимально, пpибавляя к уже подсчитаной
сумме сумму столбца. Сумму столбца тоже запоминать надо - она пpигодится пpи
движении по Y. Аналогично поступать с Y, только использовать уже посчитанные
суммы столбцев. ИМХО pассчетов будет pаз в 100 меньше.


 [за ноpмальную, единую БАЛКУ!] [телеСМИ-маздай!] [я не теp логи с 22.12.2001]

--- ifmail v.2.15dev5
 * Origin: Светлое будущее головы - череп. (2:461/214.25)