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

From

Nick Poroshin (2:5054/58.5)

To

Ilia Kantor

Date

2002-12-10T18:55:18Z

Area

RU.ALGORITHMS

Привет Ilia!

10 декабря 2002 02:54, Nick Poroshin wrote to Ilia Kantor:
 NP>  09 декабря 2002 15:03, Ilia Kantor wrote to Georgy Plechanov:
 IK>> В каждом таком прямоугольнике будем искать максимальную
 IK>> подматрицу, включающую в себя отрезки строк i..j, т.е полностью
 IK>> заполняющую прямоугольник сверху донизу.

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

 IK>> Такую подматрицу можно найти простым сканирующим алгоритмом,
 IK>> аналогично одномерному случаю.
 NP> Однако его сложность n^2 !  (т.е. n*(j-i+1)  )
Хотя можно пpедпосчитать суммы веpтик. столбцов m[0-j,i] -тогда его сложность, действительно, будет n. И, в итоге n^3.

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

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