#include <bits/stdc++.h>
using namespace std;
  
int count0(string s)
{
    
    int count = 0;
  
    
    for (int i = 0; i < s.size(); i++) {
  
        
        if (s[i] == '0') {
            count++;
        }
    }
    return count;
}
int solve(vector<string> vec, int A,
          int B, int idx,
          vector<vector<vector<int> > >& dp)
{
    
    
    if (idx == vec.size() || A + B == 0) {
        return 0;
    }
    
    if (dp[A][B][idx] > 0) {
        return dp[A][B][idx];
    }
  
    
    int zero = count0(vec[idx]);
  
    
    int one = vec[idx].size() - zero;
  
    
    
    int inc = 0;
  
    
    
    if (zero <= A && one <= B) {
        inc = 1
              + solve(vec, A - zero,
                      B - one, idx + 1, dp);
    }
  
    
    
    int exc = solve(vec, A, B, idx + 1, dp);
  
    
    dp[A][B][idx] = max(inc, exc);
  
    
    return dp[A][B][idx];
}
  
int MaxSubsetlength(vector<string> arr,
                    int A, int B)
{
    
    vector<vector<vector<int> > > dp(
        A + 1,
        vector<vector<int> >(B + 1,
                             vector<int>(arr.size() + 1,
                                         0)));
    
    return solve(arr, A, B, 0, dp);
}
  
int main()
{
    vector<string> arr = { "1", "0", "10" };
    int A = 1, B = 1;
  
    cout << MaxSubsetlength(arr, A, B);
    return 0;
}
Original page link
Best Cool Tech Gadgets
Top favorite technology gadgets
 
 
 
 
0 comments:
Post a Comment