#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