记录编号	580894	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]货币系统	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2023-07-27 15:37:39	内存使用	1.17 MiB

#include <bits/stdc++.h> 
using namespace std;
int t,n;
int a[110],s[25010];
int main(){
    freopen("2018money.in","r",stdin);
    freopen("2018money.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(s,0,sizeof(s));
        int ma = 0,ans = n;
        for(int i = 1;i <= n;i++){
            scanf("%d",&a[i]);
            ma = max(ma,a[i]);
        }
        s[0] = 1;
        for(int i = 1;i <= n;i++){
            for(int j = a[i];j <= ma;j++){
                if(s[j-a[i]])s[j]++;
            } 
        }
        for(int i = 1;i <= n;i++){
            if(s[a[i]] > 1)ans--;
        }
        printf("%d\n",ans);
    }
    
    return 0;
    
}