ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ivan Podogov                         2:5020/400     12 Dec 2002  01:47:38
 To : Alexey Burdin
 Subject : Re: задачка с acm.uva.es :)
 -------------------------------------------------------------------------------- 
 

 Hi, Alexey!
 You wrote to All on Sat, 07 Dec 2002 23:42:57 +0300:
 
  AB> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
  AB> Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
  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 - но там просто соответствующие слагаемые с
 нулевыми индексами вычёркиваются (можно там просто изначально нули в самой
 матрице прописать).
 
 Hу вот. Теперь, за линейное время вычислив 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: задачка с acm.uva.es :)   Ivan Podogov   12 Dec 2002 01:47:38   Re: задачка с acm.uva.es :)   Ivan Podogov   12 Dec 2002 11:47:47