C++での最大数

すべてのセルの値が0または1で、サイズがl x lのMの正方形の部分行列の数が最大でmaxOnesであるような、次元wxhの行列Mがあるとします。行列Mが持つことができるものの可能な最大数を見つける必要があります。

したがって、入力がw =3、h =3、l =2、maxOnes =1の場合、出力は3 * 3行列のように4になり、2*2サブ行列に複数の1を含めることはできません。 。 4つある最良の解決策は-

これを解決するには、次の手順に従います-

• ret：=0

• サイズnxn

  の2D配列sqを1つ作成します。

• 初期化i：=0の場合、i <高さの場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j <幅の場合、更新（jを1増やします）、実行-

    • sq [i mod n、jmodn]を1増やします

• 配列を定義するv

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • vの最後にsq[i、j]を挿入します

• 配列vを逆の順序で並べ替えます

• 初期化i：=0、j：=0の場合、i

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
      int ret = 0;
      vector < vector <int> > sq(n, vector <int>(n));
      for(int i = 0; i < height; i++){
         for(int j = 0; j < width; j++){
            sq[i % n][j % n]++;
         }
      }
      vector <int> v;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < n ; j++){
            v.push_back(sq[i][j]);
         }
      }
      sort(v.rbegin(), v.rend());
      for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){
         ret += v[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maximumNumberOfOnes(3,3,2,1));
}

入力

3, 3, 2, 1

出力

4