|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Cvetkov 2:5030/1334 10 Dec 2002 12:51:46
To : Georgy Plechanov
Subject : задачка с acm.uva.es :)
--------------------------------------------------------------------------------
09 Дек 02 12:38, Georgy Plechanov писал(ла) Slava Gorbanev:
AB>>>> Дана матрица 100х100 (ну или меньше) целых чисел от -127 до
AB>>>> 127. Hеобходимо найти в ней такой прямоугольник, чтобы сумма
AB>>>> всех чисел в нем была максимальна (из всех возможных
AB>>>> таких прямоугольников).
AV>>> Может быть я и ошибаюсь, но, по моему единственным решением при
AV>>> этом всегда будет прямоугольник ограничивающий собственно
AV>>> матрицу.
SG>> это не так, поскольку в матрице есть отрицательные числа.
GP> что-то мне подсказывает, что она вообще нп полная
А мне чтото подсказывает что O(n^2) Аналогичная одномерная задача решаеться,
насколко мне известно, за линейное время.
Alex Cvetkov
--- Клиент морга
* Origin: Life suxx (2:5030/1334)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
