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

Question

给你一个由 0 和 1 组成的网格，它的维度为 1 ≤⟩N,M ≤ 2500 和一个数字 0 ≤ K ≤ 6. 任务是统计网格中正好有K个矩形的个数。

它必须更快 O(N^2*M)，像 O(NMlog(N+M)) 这样的东西会起作用。我最好的方法是复杂度为 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 的一半，使水平分隔线变为垂直，这意味着我们已经为我们的调用切断了 M （我们从中绘制 O(M^2) 宽度）在 2.

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

How many rectangles contain exactly k ones on a grid N*M

algorithm

divide-and-conquer