[2018-10-21] [LeetCode-Week7] 86

https://leetcode.com/problems/score-after-flipping-matrix/description/

We have a two dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

因为二进制数高位的 1 比 后面所有的位都为 1 加起来还要大，所以只需要优先满足高位即可。
对于最高位，直接使用行变换全部置为 1.
接下来对于后面的位，没办法使用行变换（因为前面的位已经最优化），所以使用列变化使得 1 尽可能多即可。

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int n = A.size();
        int m = A[0].size();
        for (int i = 0; i < n; i++) {
            if (!A[i][0]) {
                for (int j = 0; j < m; j++) {
                    A[i][j] = 1 - A[i][j];
                }
            }
        }
        
        int ans = n * (1 << m);
        for (int j = 1; j < m; j++) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (A[i][j]) {
                    cnt++;
                }
            }
            ans += max(cnt, n-cnt) * (1 << (m-j));
        }
        
        return ans >> 1;
    }
};