Flip Elements

#include<bits/stdc++.h>
using namespace std;

vector<int> a;
// unordered_map<int, unordered_map<int, pair<int, int>>> dp;
vector<vector<pair<int, int>>> dp;

pair<int, int> rec(int i, int sum) {
    if(i == (int) a.size()) {
        if(sum >= 0) {
            return {sum, 0};
        }
        else {
            return {INT_MAX, 0};
        }
    }
    
    if(dp[i][sum].second != -1) return dp[i][sum];
    
    pair<int, int> ans1 = {INT_MAX, 0};
    if(sum - 2 * a[i] >= 0) {
        ans1 = rec(i + 1, sum - 2 * a[i]);
        ans1.second++;
    }
    pair<int, int> ans2 = rec(i + 1, sum);
    
    return dp[i][sum] = min(ans1, ans2);
}

void solve() {
    int n; cin >> n;
    a.resize(n);
    dp.assign(101, vector<pair<int, int>>(20001, make_pair(-1, -1)));
    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    
    cout << rec(0, sum).second << '\n';
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int t; cin >> t;

    while(t--) solve();
    return 0;
}