Сколько прямоугольников содержит ровно k единиц на сетке N * M

Question

Сколько прямоугольников содержит ровно k единиц на сетке N * M

function Foo(){  
   event.preventDefault(); 
 $.ajax(   {  
      url:"<?php echo base_url();?>Controllername/ctlr_function",
      type:"POST",
      data:'email='+$("#email").val(),
      success:function(msg)      {  
         alert('You are subscribed');
      }
   }   );
}

Я много раз пробовал для хорошего решения, и ответ @taufique помог мне прийти к этому ответу.

NB: Не забудьте поставить event.preventDefault(); в начале тело функции.

4

algorithm divide-and-conquer

задан Dru01 19 March 2019 в 15:21

1 ответ

Другие вопросы по тегам:

algorithm divide-and-conquer

Похожие вопросы:

score 0 · Answer 1

Один из способов получить логарифмический коэффициент - это разделить по горизонтали, добавить количество прямоугольников с K 1 с выше разделительной линии, число прямоугольников с K 1 с ниже разделительной линии ( вычисляется рекурсивно), и для каждой горизонтальной ширины (их O(|columns|^2)) количество прямоугольников, которые расширяют некоторую часть выше и некоторую часть ниже разделенной линии с той же фиксированной шириной. Мы вычислим последнее, разбив его на две части из K (максимум с 7 после K ≤ 6, и мы можем захотеть одну нулевую часть). Мы можем выполнить бинарный поиск по фиксированной ширине и нижней или верхней строке вверх или вниз по сумме префикса матрицы, которую мы можем предварительно рассчитать в O(M * N) и получить в O(1).

f(vertical_range) =
  f(top_part) +
  f(bottom_part) +
  NumTopRecs(w, i) * NumBottomRecs(w, k - i)
    where i <- [0...k],
          w <- all O(M^2) widths

Хитрость в том, что в каждом рекурсивном вызове мы поворачиваем половину, переданную в f, так, чтобы горизонтальная разделительная линия становилась вертикальной, что означает, что мы сократили M для нашего вызова (из которого мы нарисуем O(M^2) ширины) в 2.