Cho ma trận A 0/1. Một nước: chọn hàng hoặc cột, flip tất cả bit (0↔1). Sau khi flip xong, mỗi hàng đọc như số nhị phân, score = tổng các hàng. Tìm score lớn nhất.
Ví dụ: [[0,0,1,1],[1,0,1,0],[1,1,0,0]] → 39 (sau flip thành [[1,1,1,1],[1,0,0,1],[1,1,1,1]] → 15+9+15=39).
Giải pháp:
Luôn flip hàng để cột 0 thành 1 (tối ưu bit trọng số cao nhất)
Với cột j≥1: đếm cnt = số hàng có A[i][j] == A[i][0] (sau flip hàng)
Cột j đóng góp max(cnt, n-cnt) * 2^(m-j-1)
Cột 0 đóng góp n * 2^(m-1)
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int matrixScore(vector<vector<int>>& A) { int n = A.size(), m = A[0].size(); int ret = (1 << (m-1)) * n; for(int j=1;j<m;j++){ int cnt=0; for(int i=0;i<n;i++) cnt += (A[i][j]==A[i][0]); int temp = (1 << (m-j-1)) * max(cnt, n-cnt); ret += temp; } return ret; } }; int main(){ vector<vector<int>> v={{0,0,1,1},{1,0,1,0},{1,1,0,0}}; Solution ob; cout << ob.matrixScore(v); }Đầu vào
[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Đầu ra
39