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

From

Alexey Burdin (2:5012/32.768)

To

Anton Kuznetsov

Date

2002-12-09T02:43:40Z

Area

RU.ALGORITHMS

> from: /Unknown/
Как после вчерашнего, Anton ?

 14:14 Воскресенье Декабрь 08 2002, Anton Kuznetsov --> Alexey Burdin:

 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 минут :)

 AK>  А как ты считал сумму в каждом прямоугольнике?
 AK>  Я бы делал примерно то же самое, только динамически.
    А в чём разница, я не уловил :)
 AK>  Т.е для каждой клетки (считая, что она - левый верхний угол) и для
 AK> всех возможных длин и ширин :) прямоугольников считал бы эту сумму, а
 AK> потом выбирал максимум - вроде так не должно много работать...
    Однако порядка 100^6 операций извлечения из 2-мерного массива и
    суммирования :(
    Исходник ушел нетмылом :) А ты проверь. Напиши и проверь :)
  2All: Оптимизацию/другой алгоритм хочу!

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: No, GWC (2:5012/32.768)