Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Kuznetsov                      2:5030/566.13  08 Dec 2002  15:14:00
 To : Alexey Burdin
 Subject : задачка с acm.uva.es :)
 -------------------------------------------------------------------------------- 
 
 
  AB>     Дана матрица 100х100 (ну или меньше) целых чисел от -127 до 127.
  AB>     Hеобходимо найти в ней такой прямоугольник, чтобы сумма всех чисел
  AB>     в нем была максимальна (из всех возможных таких прямоугольников).
  AB>
  AB>     Hа ум (?) сразу приходит полный перебор: 1<=x1,y1<=100 , x1<=x2<=100,
  AB>     y1<=y2<=100, s=sum a[y,x] x1<=x<=x2, y1<=y<=y2.
  AB>     Для матрицы 100х100 считал на Celeron 466 аж 15 минут :)
 
  А как ты считал сумму в каждом прямоугольнике?
  Я бы делал примерно то же самое, только динамически.
  Т.е для каждой клетки (считая, что она - левый верхний угол) и для всех
 возможных длин и ширин :) прямоугольников считал бы эту сумму, а потом выбирал
 максимум - вроде так не должно много работать...
 
                             До свидания, Alexey!
  * Origin: ФТШ - школа наша! (2:5030/566.13)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 задачка с acm.uva.es :)   Alexey Burdin   08 Dec 2002 00:42:57 
 задачка с acm.uva.es :)   Anton Kuznetsov   08 Dec 2002 15:14:00 
 задачка с acm.uva.es :)   Alexey Burdin   09 Dec 2002 03:43:40 
 Re: задачка с acm.uva.es :)   Vladislav Gusev   09 Dec 2002 17:15:42 
 Re: задачка с acm.uva.es :)   Vladislav Gusev   09 Dec 2002 19:25:40 
 задачка с acm.uva.es :)   Sasha Pelepeichenko   09 Dec 2002 00:50:39 
 Re: задачка с acm.uva.es :)   Sergey Andrianov   09 Dec 2002 00:23:44 
Архивное /ru.algorithms/39343df32a61.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional