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

From

Anton Kuznetsov (2:5030/566.13)

To

Alexey Burdin

Date

2002-12-08T14:14Z

Area

RU.ALGORITHMS

                Всех тебе благ, Alexey!

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

 А как ты считал сумму в каждом прямоугольнике?
 Я бы делал примерно то же самое, только динамически.
 Т.е для каждой клетки (считая, что она - левый верхний угол) и для всех
возможных длин и ширин :) прямоугольников считал бы эту сумму, а потом выбирал
максимум - вроде так не должно много работать...

                            До свидания, Alexey!
 * Origin: ФТШ - школа наша! (2:5030/566.13)