有多少个矩形在网格N * M上恰好包含k个矩形

Question

给出一个0和1的网格，它的尺寸1≤N，M≤2500，数字0≤K≤6。任务是计算网格中正好有K个矩形的矩形数。

它必须更快O（N ^ 2 * M），类似O（NMlog（N + M））将起作用。我最好的aproach是一个复杂度为O（N ^ 2 * M）的dp，但这是缓慢的，我被告知答案是分而治之但我无法得到它。任何的想法？

Answer 1

获得对数因子的一种方法是水平划分，在分界线上方添加K 1s的矩形数，在分界线下方（递归计算）的K 1s的矩形数，并且对于每个水平宽度，（有它们的O(|columns|^2)）在具有相同固定宽度的划分线上方和部分下方延伸某些部分的矩形的数量。我们通过分成K的两部分分区来计算最后一个分区（自K ≤ 6起最大值为7，我们可能希望一部分为零）。我们可以在矩阵前缀和上以固定宽度和底线或顶线（向上或向下）进行二分搜索，我们可以在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的一半，使得水平分隔线变为垂直，这意味着我们在2中切割M用于我们的调用（从中我们绘制O(M^2)宽度）。