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

From

Nick Poroshin (2:5054/58.5)

To

Ilia Kantor

Date

2002-12-10T02:54:46Z

Area

RU.ALGORITHMS

Привет Ilia!

 09 декабря 2002 15:03, Ilia Kantor wrote to Georgy Plechanov:
 AB>>>>> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до
 AB>>>>> 127. Необходимо найти в ней такой прямоугольник, чтобы сумма
 AB>>>>> всех чисел в нем была максимальна (из всех возможных
 AB>>>>> таких прямоугольников).
 IK> Перебираем все прямоугольники, состоящие из соседних строк

 IK> for(i=0;i<100;i++)
 IK>   for(j=i;j<100;j++)
 IK>     { обработать прямоугольник из строк i..j }

 IK> В каждом таком прямоугольнике будем искать максимальную подматрицу,
 IK> включающую в себя отрезки строк i..j, т.е полностью заполняющую
 IK> прямоугольник сверху донизу.

 IK>  * * * * * * *
 IK>  * [* * * *] *  i
 IK>  * [* * * *] *
 IK>  * [* * * *] *  j
 IK>  * * * * * * *

 IK> Такую подматрицу можно найти простым сканирующим алгоритмом,
 IK> аналогично одномерному случаю.
Однако его сложность n^2 !  (т.е. n*(j-i+1)  )

 IK> Итого, алгоритм имеет сложность n^3 = 10^6 операций. Быстрее можно, но
                                     n^4 !
 IK> не так, чтобы намного. Квадратичный алгоритм мне неизвестен, да и
 IK> вряд
 IK> ли есть.

С уважением, Poroshin Nick

---
 * Origin: Default origin (2:5054/58.5)