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

From

Andrew Ezhguroff ()

To

Anthony Volkov

Date

2002-12-09T04:34:09Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Anthony Volkov" <anthonyv@mail.redcom.ru>  сообщил(а):

 AB>>     Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
 AB>>     Необходимо найти в ней такой прямоугольник, чтобы сумма всех
 AB>> чисел     в нем была максимальна (из всех возможных таких
 AB>> прямоугольников).
 AV> Может быть я и ошибаюсь, но, по моему единственным решением при этом
 AV> всегда будет прямоугольник ограничивающий собственно матрицу.

Ошибаешься. Посмотри на диапазон чисел. А теперь представь себе, например,
матрицу, в которой первый и последний столбец - сплошь -127. Удаление этих
столбцов безусловно увеличит сумму.

С уважением, Андрей.


-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)