3

给定一个N x N矩阵，其中N <= 25和每个单元格都有一个正整数值，您如何将其划分为最多 K 行（直线上/下线或直线左/右线 [注意：它们必须从一侧延伸到其他]）以便最大值组（由分区确定）最小？

例如，给定以下矩阵

1 1 2
1 1 2 
2 2 4

并且我们可以使用 2 行来划分它，我们应该在第 2 列和第 3 列之间画一条线，以及在第 2 和第 3 行之间画一条线，它给出了最小化的最大值 4。

我的第一个想法是用一个位掩码来表示每行的状态，用 2 个整数来表示它。但是，这太慢了。我认为复杂性是O(2^(2N))也许你可以为行解决它，然后为列解决它？

有人有想法么？

编辑：这是我用谷歌搜索后的问题：http ://www.sciencedirect.com/science/article/pii/0166218X94001546

另一篇论文：http ://cis.poly.edu/suel/papers/pxp.pdf

我试着读那个^

4

1 回答 1

0

您可以尝试垂直线的所有子集，然后对水平线进行动态规划。

假设您已将垂直线集固定为 S。将包含固定垂直线集 S 的矩阵的前 K 行的子问题的答案表示为 D(K, S)。然后找到一个递归来解决具有较小子问题的 D(K, S) 是微不足道的。

如果您在开始时预先计算每个子矩阵的大小，则总体复杂度应为 O(2^N * N^2)。

于 2013-02-25T14:34:56.103 回答