|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 09 Dec 2002 00:23:44
To : Alexey Burdin
Subject : Re: задачка с acm.uva.es :)
--------------------------------------------------------------------------------
Однажды 07-Dec-02 в 23:42 Alexey Burdin (2:5012/32.768)
написал All по поводу
-=- задачка с acm.uva.es :) -=-
AB> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
AB> Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
AB> в нем была максимальна (из всех возможных таких прямоугольников).
AB> Hа ум (?) сразу приходит полный перебор: 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> желательно чтобы работало на "раз-два-три".
Постарайся учесть, что если известна сумма для одного прямоугольника, то при
сдвигании его на одну клетку нет необходимости вычислять сумму целиком,
достаточно вычесть строку/столбец с одной стороны и прибавить - с другой. При
этом строки/столбцы определенной длины могут быть вычислены заранее и с
использованием такой же оптимизации, т.е. верхняя строка столбцов считается
целиком, а со второй и ниже - путем прибавления/вычитания по одному числу.
Думаю, объем вычислений таким образом можно значительно сократить.
До свидания, в 23:19 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
