|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Poroshin 2:5054/58.5 10 Dec 2002 03:54:46
To : Ilia Kantor
Subject : задачка с acm.uva.es :)
--------------------------------------------------------------------------------
09 декабря 2002 15:03, Ilia Kantor wrote to Georgy Plechanov:
AB>>>>> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до
AB>>>>> 127. Hеобходимо найти в ней такой прямоугольник, чтобы сумма
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
