|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sasha Pelepeichenko 2:461/214.25 09 Dec 2002 00:50:39
To : Alexey Burdin
Subject : задачка с acm.uva.es :)
--------------------------------------------------------------------------------
07 Dec 02 Alexey Burdin write to All about "задачка с acm.uva.es :)":
AB> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
AB> Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
AB> в нем была максимальна (из всех возможных таких прямоугольников).
AB> Hа ум (?) сразу приходит полный перебор: 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
