C++の1と0

それぞれm0sとn1sのドミネーターがあるとします。一方、バイナリ文字列の配列があります。ここでのタスクは、指定されたm0とn1で生成できる文字列の最大数を見つけることです。 0と1はそれぞれ最大1回使用できます。したがって、入力がArray =[“ 10”、“ 0001”、“ 111001”、“ 1”、“ 0”、]であり、m=5およびn=3の場合、出力は4になります。 「10」、「0001」、「1」、「0」である50と31を使用して、合計4つのストリングを形成できます。

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

• サイズ（m + 1）x（n + 1）の行列を作成します
• ret：=0
• 0からstrs配列のサイズまでの範囲のiの場合
  • 1：=0、0：=0
  • 範囲0からstrs[i]のサイズのjの場合
    • star [i、j]が1の場合は1を増やし、0の場合は0を増やします
  • mから0までの範囲のjの場合
    • nから1までの範囲のjの場合
      • dp [j、k]：=最大dp [j、k]および1 + dp [j –ゼロ、k-1]
      • ret：=retとdp[j、k]の最大値
• return ret

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int findMaxForm(vector<string>& strs, int m, int n) {
      vector < vector <int> > dp(m + 1, vector <int>(n + 1));
      int ret = 0;
      for(int i = 0; i < strs.size(); i++){
         int one = 0;
         int zero = 0;
         for(int j = 0; j < strs[i].size(); j++){
            one += strs[i][j] == '1';
            zero += strs[i][j] == '0';
         }
         for(int j = m; j>= zero; j--){
            for(int k = n; k >= one; k--){
               dp[j][k] = max(dp[j][k], 1 + dp[j - zero][k - one]);
                  ret = max(ret, dp[j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"10","0001","111001","1","0"};
   Solution ob;
   cout << (ob.findMaxForm(v, 5, 3));
}

入力

["10","0001","111001","1","0"]
5
3

出力

4