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

From

Ivan Podogov ()

To

Alexey Burdin

Date

2002-12-12T00:47:38Z

Area

RU.ALGORITHMS

From: "Ivan Podogov" <bgd_soft@mtu-net.ru>

Hi, Alexey!
You wrote to All on Sat, 07 Dec 2002 23:42:57 +0300:

 AB> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
 AB> Необходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
 AB> в нем была максимальна (из всех возможных таких прямоугольников).
[skip]
 AB> Хотелось бы что-нибудь более оптимальное, но влезающее в
 AB> досовые 400к :), желательно чтобы работало на "раз-два-три".

Сегодня много думали всей компашкой, и пришли к выводам...

Во-первых, заводим вторую матрицу (назовём её B), которая для каждого элемента
[i, j] исходной хранит сумму всех чисел в прямоугольнике [1..i]x[1..j], т.е. в
подматрице от левого верхнего угла до этого элемента. Такая матрица (кстати,
тип данных - long, ибо 127x100x100) считается за линейное время:

Для первой строки и первого столбца - вычисления тривиальны;
далее - "сканирующими линиями", для каждого элемента берём разницу того, что
хранится для левого от него и для того, что слева-вверху (это даст сумму чисел
в строке), плюс то, что сверху и плюс сам элемент:
B[i, j] := B[i-1, j] + B[i, j-1] + A[i, j] - B[i-1, j-1];

А теперь - зачем нам эта матрица :). Ясно, что она влезет в твои 400К (скажу
больше - в 40К). А вот легче жить стало - по самое не балуйся:
Для вычисления суммы элементов матрицы в прямоугольнике, скажем,
[i1..i2]x[j1..j2]:
S(i1,i2, j1,j2) := B[i2, j2] - B[i1-1, j1] - B[i1, j1-1] + B[i1-1, j1-1].

Тут надо учитывать i1=1 и j1=1 - но там просто соответствующие слагаемые с
нулевыми индексами вычёркиваются (можно там просто изначально нули в самой
матрице прописать).

Ну вот. Теперь, за линейное время вычислив B, сумму подматриц находим "на
раз".
Остались "два-три" :). Гоняем перебор по всем подматрицам:
i1 = 1..m, i2 = i1..m - даёт m*(m+1)/2;
j1 = 1..n, j2 = j1..n - n*(n+1)/2.
Итого - квадратичное время от количества ячеек. Для 100х100 это будет
25 502 500 - в принципе, за пару секунд (или даже меньше одной - в зависимости
от компа) посчитает.

Сойдёт?

~~~~~~~~~~~~~~~~~~
With best regards,
Ivan "BGD" Podogov


--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)