ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Protopopov Michael                   2:5020/400     04 Feb 2002  21:58:22
 To : Anton Svatkov
 Subject : Re: муха
 -------------------------------------------------------------------------------- 
 

     По C-шной привычке индексы массива считаю начинающимися с 0.
     Пробегаемся по массиву вычисляя для каждой клетки кол-во мух сидящих в
 прямоугольнике (0, 0)-(i,j), т.е слева и выше от текущей клетки. Hазовем это
 число S(i, j). Очевидно, что S(i, j) = S(i-1, j) + S(i, j-1) - S(i-1, j-1) +
 <кол-во мух в поле (i, j)>. При этом, если хотя бы один инекс отрицательный
 S(i, j) = 0.
     Паралельно с этим вычиляем число мух накрываемых мухобойкой (можно
 начинать с (19, 19)), правый нижний угол которой расположен в точке (i, j).
 Это число равно S(i, j) - S(i-20, j) - S(i, j-20) + S(i-20, j-20). А уж
 отследить точку, в которой это чило максимально - элементарно.
     Данный алгоритм легко обобщается на произвольные размеры поля и
 мухобойки даже если прямоугольную мухобойку можно поворачивать на 90
 градусов. Его сложность O(m*n), где m на n - размер поля.
 -- 
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.Mail.Ru (2:5020/400)
 
 

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