代码

#include<bits/stdc++.h>
using namespace std;
inline int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        //if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}

const int M=25010,N=110;

int f[M],a[N];

int main(){
    int t=getint(),n,mx=0;
    while(t--){
        n=getint();
        for(register int i=0;i<n;++i)mx=max(a[i]=getint(),mx);
        sort(a,a+n);
        memset(f,0,sizeof(f));
        f[0]=1;
        int ans=n;
        for(register int i=0;i<n;++i){
            if(f[a[i]]){
                --ans;
                continue;
            }
            for(register int j=a[i];j<=mx;j++)if(f[j-a[i]])f[j]=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

评测结果