คะแนนหลังจากพลิกเมทริกซ์ใน C ++

สมมติว่าเรามีเมทริกซ์ A สองมิติ โดยที่แต่ละค่าเป็น 0 หรือ 1 ในที่นี้ การย้ายประกอบด้วยการเลือกแถวหรือคอลัมน์ใดๆ และสลับแต่ละค่าในแถวหรือคอลัมน์นั้น:เปลี่ยน 0 ทั้งหมดเป็น 1 วินาที และ 1 เป็น 0 ทั้งหมด หลังจากทำการย้ายจำนวนเท่าใดก็ได้ ทุกแถวของเมทริกซ์นี้จะถูกตีความว่าเป็นเลขฐานสอง และคะแนนของเมทริกซ์คือผลรวมของตัวเลขเหล่านี้ ดังนั้นงานของเราคือการหาคะแนนสูงสุดที่เป็นไปได้ หากอินพุตเป็นแบบ −

ผลลัพธ์จะเป็น 39 หลังจากสลับแล้วเมทริกซ์จะเป็น -

ดังนั้นตัวเลขก็คือ 15 + 9 + 15 =39

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=จำนวนแถวและ m :=จำนวนคอลัมน์

• ret :=n x (2^(m – 1))

• สำหรับ j ในช่วง 1 ถึง m – 1

  • cnt :=0

  • สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

    • cnt :=cnt + A[i, j] =A[i, 0]

  • temp :=2^(m – j – 1) * maximum of cnt and n – cnt

  • ret :=ret + ชั่วคราว

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int matrixScore(vector<vector<int>>& A) {
      int n = A.size();
      int 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;
   }
};
main(){
   vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
   Solution ob;
   cout << (ob.matrixScore(v));
}

อินพุต

[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

ผลลัพธ์

39