题目分析

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110 , M = 25010;
int q[N];
bool f[M];
int n;
int main() {

    int T;
    cin >> T;
   // for (int i = 1 ; i <= n ; i ++ ) cin >> q[i];

    while (T -- ) {
        int n;
        cin >> n;
        for (int i = 1 ; i <= n ; i ++ ) cin >> q[i];

        sort(q + 1 , q + n + 1);
        int m = q[n];
        memset(f,false,sizeof f);
        f[0] = true;
        int k = 0;
        for (int i = 1 ; i <= n ; i ++ ) {

            if (!f[q[i]]) k ++;
            for (int j = q[i] ; j <= m ; j ++ ) {
                f[j] = f[j] |  f[j - q[i]]; // 异或运算 如果 f[j] 能被 f[j - q[i]] 所表示，那么排除
            }
        }
        cout << k << endl;
    }


    return 0;
}