翻转矩阵后的得分

记牢这把尺子:首列必须全 1(最高位优先),其余每列让 1 尽量多——1 少于 0 才翻、相等不动,最终 1 不少于 0。下面每一帧都在套它。

输入矩阵 · 3×4 · 绿=1 蓝=0：这是原始矩阵,绿色格是 1、蓝色格是 0。我们先处理行、再处理列。先想清楚:每行的最左边是最高位,一个高位的 1 抵得上后面好几位,所以最该先抢的就是首列。

第一步 · 逐行看首位：紫色这一列是首列,也就是每行的最高位。我们一行一行检查它的首位:是 1 就不动,是 0 就把整行翻过来。先从第 0 行开始。

第 0 行 · 首位 = 0：轮到第 0 行,内容是 [0, 0, 1, 1]。它的首位是 0。首位是 0,最高位还没抢到手,这一整行得翻一次。

翻转第 0 行：整行翻过来(红色闪一下),第 0 行变成 [1, 1, 0, 0],首位现在是 1,最高位拿下了。

第 1 行 · 首位 = 1：轮到第 1 行,内容是 [1, 0, 1, 0]。它的首位是 1。首位已经是 1,最高位到手,这一行不用动。

第 1 行保持不动：第 1 行原样保留,首位本来就是 1,白翻还会把它弄丢,不动它。

第 2 行 · 首位 = 1：轮到第 2 行,内容是 [1, 1, 0, 0]。它的首位是 1。首位已经是 1,最高位到手,这一行不用动。

第 2 行保持不动：第 2 行原样保留,首位本来就是 1,白翻还会把它弄丢,不动它。

第一步完成 · 首列全是 1：第一步收工。看紫色的首列,现在三个格全是 1,每一行的最高位都抢到了手。矩阵变成 [1,1,0,0]、[1,0,1,0]、[1,1,0,0]。接下来处理其余各列,让低位也尽量多挣分。

第二步 · 逐列数 1 的个数：第二步换个方向,逐列看。每一列数一数有几个 1,如果 1 的个数少于 0,就把整列翻过来;相等就不翻,目标是让每列 1 不少于 0。注意首列已经全是 1 了,翻它只会变差,所以从第 1 列起真正可能动手。

第 0 列 · 1 的个数 = 3：看第 0 列(紫色),从上到下是 [1, 1, 1]。数一下:1 有 3 个,0 有 0 个。这是首列,刚抢成全 1,自然不用翻。

第 0 列保持不动：第 0 列保持不动,1 本来就有 3 个、不少于 0,翻了反而变少。

第 1 列 · 1 的个数 = 2：看第 1 列(紫色),从上到下是 [1, 0, 1]。数一下:1 有 2 个,0 有 1 个。1 不少于 0,保持不动。

第 1 列保持不动：第 1 列保持不动,1 本来就有 2 个、不少于 0,翻了反而变少。

第 2 列 · 1 的个数 = 1：看第 2 列(紫色),从上到下是 [0, 1, 0]。数一下:1 有 1 个,0 有 2 个。1 少于 0,这一列翻过来更划算。

翻转第 2 列：整列翻过来(红色闪一下),第 2 列变成 [1, 0, 1],现在 1 有 2 个,1 不少于 0 了。

第 3 列 · 1 的个数 = 0：看第 3 列(紫色),从上到下是 [0, 0, 0]。数一下:1 有 0 个,0 有 3 个。1 少于 0,这一列翻过来更划算。

翻转第 3 列：整列翻过来(红色闪一下),第 3 列变成 [1, 1, 1],现在 1 有 3 个,1 不少于 0 了。

第二步完成 · 每列 1 不少于 0：第二步收工,矩阵不再翻动了。现在每一行是 [1111]、[1001]、[1111]。最后一步,把每一行当成二进制数算出来,再加到一起。

第 0 行二进制 = 1111 = 15：把第 0 行(紫色)按二进制读:1111,换成十进制就是 15。累计得分加上它,现在是 15。

第 1 行二进制 = 1001 = 9：把第 1 行(紫色)按二进制读:1001,换成十进制就是 9。累计得分加上它,现在是 24。

第 2 行二进制 = 1111 = 15：把第 2 行(紫色)按二进制读:1111,换成十进制就是 15。累计得分加上它,现在是 39。

全部完成 · 最大得分 = 39：三行加起来:15 加 9 加 15,等于 39。这就是最大得分。先翻行保最高位、再翻列让每列 1 不少于 0,这套贪心一定最优。

边界先想清:单格非 0 即 1 答案都是 1;全 0 矩阵翻完每行也能凑满。

两个高频追问:两步各自局部最优叠成全局最优;列可用计数公式免去真翻。