algorithm - 将 k 个石头放在 * m 网格上，以最大化每个角有一颗石头的矩形数量

Question

将k颗石子放在一个*m的格子上，每颗石子都应该在格子线的交点上。尝试找到一种放置石子的方法，以使每个角有一颗石子的矩形数量最大化. 输出号码。

例如，如果 k <= 3，则答案为 0，表示没有这样的矩形；如果 k 为 4 且 n, m >= 2，则答案为 1；更多示例：

(n, m, k, 答案): (3, 3, 8, 5), (4, 5, 13, 18), (7, 14, 86, 1398)

k 介于 0 和 n * m 之间。n, m 是小于 30000 的正整数

ps：这其实是微软编程之美资格赛的一个问题（但你可能找不到，因为它在中国举办，我自己翻译成英文。） pss：我已经取得了一些进展。可以证明，要得到答案，搜索所有可能的 Ferrers 图就足够了，但复杂度相对于 k 呈指数级。

编辑：（杜克林）

(3, 3, 8, 5) 的可视化，矩形以不同的颜色表示。

正如您所注意到的，它实际上是一个 (n-1) * (m-1) 网格，还有另一种解释是使用 * m 网格，其中石头放置在单元格内，但是您需要添加一个额外的约束，即矩形不能是宽度/高度 1。

Answer 1

从编程的角度来看，这表明搜索利用矩形的对称性来减少搜索空间。接下来是一个扩展的提示。

正如 OP 指出的那样，一个简单的实现将检查所有可能的节点 k 子集，大小为 C(nm,k)。

搜索空间的减少量取决于如何利用对称性。正方形具有反射和旋转的对称性，因此对于 n=m，有一个 8 倍对称群。如果说 n < m，那么较少的对称性给出一个 4 倍群。

一种典型的方法是按字典顺序组织可能的 k 子集，以便当潜在配置等同于该顺序中较早出现的配置时，它会被跳过。

但是还有额外的“环绕”对称性需要利用。假设网格的最后一行移动到顶部（连同任何分配给其节点的石头）。此转换保留了 4 石矩形的计数（尽管这些矩形的确切大小会有所不同）。

实际上，转置两行或两列可以保留 4 石矩形的计数。一旦你有了洞察力，你能看到如何更有效地参数化搜索空间吗？

补充： 尽管它比编程更多的是数学洞察力，但请考虑“完整子矩形”提供的 4 石矩形的数量，如果 rc < k 则说 rxc。考虑多一颗石头提供的额外矩形的增量；再多两块石头。