Điểm tối đa sau khi lật ma trận nhị phân tối đa K lần trong C++

Mô tả bài toán

Cho ma trận nhị phân mat (0/1) và số K. Mỗi lần lật chọn một hàng hoặc cột, đổi 0↔1. Tối đa K lần lật. Mỗi hàng tạo thành số nhị phân (bit trái trọng số cao nhất). Tối đa hóa tổng các hàng.

Giải pháp (Tham lam)

• Ưu tiên làm cột 0 toàn 1 (bit quan trọng nhất): lật hàng có mat[i][0] == 0.
• Với các cột sau, nếu số 0 > số 1 và còn lượt lật → lật cột đó.
• Dùng map để ưu tiên lật hàng có giá trị tăng thêm lớn nhất trước.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;
const int row = 3, col = 3;

int MaxSumAfterFlip(int mat[row][col], int K) {
    map<int, int> flipValues;
    int updateVal, MaxSum = 0;
    for (int i = 0; i < row; ++i) {
        if (mat[i][0] == 0) {
            updateVal = 0;
            for (int j = 1; j < col; ++j)
                updateVal += mat[i][j] * pow(2, col - j - 1);
            flipValues[updateVal] = i;
        }
    }
    auto it = flipValues.begin();
    while (K > 0 && it != flipValues.end()) {
        int idx = it->second;
        for (int j = 0; j < col; ++j) mat[idx][j] = (mat[idx][j] + 1) % 2;
        ++it; --K;
    }
    for (int j = 0; j < col; ++j) {
        int zeros = 0, ones = 0;
        for (int i = 0; i < row; ++i) mat[i][j] == 0 ? zeros++ : ones++;
        if (K > 0 && zeros > ones) { MaxSum += zeros * pow(2, col - j - 1); --K; }
        else MaxSum += ones * pow(2, col - j - 1);
    }
    return MaxSum;
}

int main() {
    int mat[row][col] = {{1,0,0},{0,1,1},{1,0,1}};
    int K = 2;
    cout << "The Maximum score after flipping the matrix atmost K times is " << MaxSumAfterFlip(mat, K);
    return 0;
}

Đầu ra

The Maximum score after flipping the matrix atmost K times is 19