题目链接

Osenbei Aizu - 0525

思路

R比较小， 所以 搜索行翻不翻， 列去0,1个数的最大值。

本题用到取反， 比较特殊，一般情况下，dfs后要把状态回滚。

时间复杂度

$$ O(RC2^R) $$

代码

#include <cstdio>
#include <bitset>

using namespace std;

bitset<10000> bt[10];
int n, m, ans;

void dfs(int x) {
    if (x == n) {
        int sum = 0;
        for (int i = 0; i < m; i++) {
            int w = 0;
            for (int j = 0; j < n; j++) {
                w += bt[j][i];
            }
            sum += max(w, n - w);
        }
        ans = max(ans, sum);
        return;
    }
    dfs(x + 1);
    bt[x].flip();
    dfs(x + 1);
}

int main() {
    while (scanf("%d%d", &n, &m), n + m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int x;
                scanf("%d", &x);// don't forget &
                bt[i][j] = x;
            }
        }
        ans = 0;
        dfs(0);
        printf("%d\n", ans);
    }
    return 0;
}