题解 | 翻之

深度优先+剪枝

每一行无非翻或者不翻，把所有情况遍历

只在沉底时，看结果是否满意（计算并更新每种情况最多1的个数）

深度优先搜索：

继续往左走

继续往右走

剪枝：

计算当前统计结果中1的数目，如果为零，或已经小于存在过的结果，直接退出

翻：二进制否运算

统计1的数量：二进制与运算

import sys

sys.setrecursionlimit(4000)
try:
    # 深度优先剪枝
    n,m = map(int,input().split(" "))
    num = []
    for i in range(n):
        s = input()
        num.append(s)

    L = n-1
    tag = int('1'*m,2)
    result = 0
    def countmax1(i,num,text):
        global result
        count = bin(text).count("1")
        if count==0 or count<result:
            # 剪枝
            return
        if i==L:
            # 沉底更新最终结果
            a1 = int(num[i],2)
            a2 = a1^tag
            result = max(result,bin(a1&text).count("1"),bin(a2&text).count("1"))
            return
        a1 = int(num[i],2)
        a2 = a1^tag
        countmax1(i+1,num,text&a1) #不翻下一行
        countmax1(i+1,num,text&a2) #翻下一行
        return
    countmax1(0,num,tag)
    print(result)
except Exception as e:
    print(e)