代码

#include <stdio.h>
#include <stdlib.h>
int a[105]; char dp[26000];
int cmp(const void *x, const void *y){ return *(int*)x - *(int*)y; }
int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        int i; for(i=0;i<n;i++) scanf("%d", &a[i]);
        qsort(a, n, sizeof(int), cmp);
        int mx = a[n-1];
        for(i=0;i<=mx;i++) dp[i]=0;
        dp[0]=1;
        int ans=0;
        for(i=0;i<n;i++){
            if(!dp[a[i]]) ans++;
            for(int v=a[i];v<=mx;v++) if(dp[v-a[i]]) dp[v]=1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

评测结果