|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/175.2 09 Dec 2002 16:03:59
To : Georgy Plechanov
Subject : задачка с acm.uva.es :)
--------------------------------------------------------------------------------
Mon Dec 09 2002 12:38, Georgy Plechanov wrote to Slava Gorbanev:
AB>>>> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
AB>>>> Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех
AB>>>> чисел в нем была максимальна (из всех возможных таких
AB>>>> прямоугольников).
Перебираем все прямоугольники, состоящие из соседних строк
for(i=0;i<100;i++)
for(j=i;j<100;j++)
{ обработать прямоугольник из строк i..j }
В каждом таком прямоугольнике будем искать максимальную подматрицу, включающую
в себя отрезки строк i..j, т.е полностью заполняющую прямоугольник сверху
донизу.
* * * * * * *
* [* * * *] * i
* [* * * *] *
* [* * * *] * j
* * * * * * *
Такую подматрицу можно найти простым сканирующим алгоритмом, аналогично
одномерному случаю.
Итого, алгоритм имеет сложность n^3 = 10^6 операций. Быстрее можно, но не так,
чтобы намного. Квадратичный алгоритм мне неизвестен, да и вряд ли есть.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
задачка с acm.uva.es :) 
