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

From

Sergey Andrianov (2:5020/1507.400)

To

Alexey Burdin

Date

2002-12-08T23:23:44Z

Area

RU.ALGORITHMS

Здравствуй, Alexey!

Однажды 07-Dec-02  в 23:42   Alexey Burdin (2:5012/32.768)
написал       All    по поводу
-=-   задачка с acm.uva.es :)  -=-

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>    желательно чтобы работало на "раз-два-три".

	Постарайся учесть, что если известна сумма для одного прямоугольника, то при сдвигании его на одну клетку нет необходимости вычислять сумму целиком, достаточно вычесть строку/столбец с одной стороны и прибавить - с другой. При этом строки/столбцы определенной длины могут быть вычислены заранее и с использованием такой же оптимизации, т.е. верхняя строка столбцов считается целиком, а со второй и ниже - путем прибавления/вычитания по одному числу. Думаю, объем вычислений таким образом можно значительно сократить.

                  До свидания,  в  23:19 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)