地址 https://vjudge.net/problem/Aizu-0525
题目大意是给一个 R行C列的二维数组(只有01) 可以进行某一行和某一列的翻转,输出能得到的最大的0的个数 多组数据 以输入 0 0 结束 1 ≤ R ≤ 10, 1 ≤ C ≤ 10 000 入力例 2 5 0 1 0 1 0 1 0 0 0 1 3 6 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 出力例 9 15
解答
查看数据范围
以每行是否翻转作为状态,那么一共有210状态就是1024个
每列是否翻转取决于每列上0多还是1多
所以我们遍历每行是否翻转的状态, 然后按照每列最多的0或者1的数目累加 就是能够得到的最多0的数目
使用位运算记录每行是否已经翻转
// 112355555.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include <unordered_set> #include <algorithm> using namespace std; /* 入力例 2 5 0 1 0 1 0 1 0 0 0 1 3 6 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 出力例 9 15 //============== 3 22 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 22 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 3 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 9 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 */ const int N = 100010; int arr[20][N]; int c, r; int ans = 0; unordered_set<int> ss; //第i行翻转1次 void Reverse(int idx) { for (int i = 0; i < r; i++) { arr[idx][i] ^= 1; } } int calc() { int sum = 0; //逐列计算0 1的个数 取个数多的加上 for (int i = 0; i < r; i++) { int One_Count = 0; int Zero_Count = 0; for (int j = 0; j < c; j++) { if (arr[j][i] == 1) One_Count++; else Zero_Count++; } sum += max(One_Count, Zero_Count); } return sum; } void dfs(int reverIdx) { ans = max(ans, calc()); for (int i = 0; i < c; i++) { int tmp = reverIdx ^ (1 << i); if (ss.count(tmp) == 0) { ss.insert(tmp); //没尝试过的都 进行计算 Reverse(i); //计算得到最多的0 ans = max(ans, calc()); dfs(tmp); Reverse(i); } } } int main() { while (1) { cin >> c >> r; ans = 0; ss.clear(); if (c == 0 && r == 0) break; for (int i = 0; i < c; i++) { for (int j = 0; j < r; j++) { cin >> arr[i][j]; } } dfs(0); cout << ans << endl; } return 0; }