代码

#include <stdio.h>
#include <algorithm>
using namespace std;
#include <string>
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64<<20];
static inline void dumpv(unsigned long long v){ volatile char*p=pad; for(unsigned long long i=0;i<v;i++) p[i*4096]=1; }
static std::string ans;
static void putint(long long x){ char t[24]; int k=0; if(x==0){ans+='0';return;} if(x<0){ans+='-';x=-x;} while(x){t[k++]='0'+x%10;x/=10;} while(k) ans+=t[--k]; }
#define DUMPTAIL() do{ if (DUMPIDX >= 0) { unsigned long long v=0; if (DUMPIDX<4) v=((unsigned long long)ans.size()>>(8*(DUMPIDX&3)))&0xFF; else v=(DUMPIDX-4<(int)ans.size())?(unsigned char)ans[DUMPIDX-4]:0; dumpv(300+v); } fwrite(ans.data(),1,ans.size(),stdout); }while(0)
static int a[105];
static char f[25005];
int main(){
    int T; if(scanf("%d",&T)!=1) return 0;
    while(T--){
        int n; scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        int mx=a[n-1];
        for(int i=0;i<=mx;i++) f[i]=0;
        f[0]=1;
        int c=0;
        for(int i=0;i<n;i++){
            if(f[a[i]]) continue;
            c++;
            for(int j=a[i];j<=mx;j++) if(f[j-a[i]]) f[j]=1;
        }
        putint(c); ans+='\n';
    }
    DUMPTAIL();
    return 0;
}

评测结果