给定一个 行 列的 0-1 矩阵。你可以对矩阵的行进行任意次重排(即任意交换两行的位置),但不能改变列的顺序。请问,在最优的行排列下,矩阵中最大的全 子矩阵(即所有元素均为 的矩形)的面积最大是多少?
第一行两个整数 ,分别表示矩阵的行数和列数。 接下来 行,每行 个整数,表示矩阵中的元素(每个数为 或 )。
一个整数,表示最大可能的全 子矩阵的面积。
4 5 10101 11011 11111 10010
6
一种可行的行重排方式为:
1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 0
此时,选取第 列到第 列、第 行到第 行的子矩阵(即 )面积为 。可以证明这是最优的。
· · 矩阵元素均为 或