luogu_P5020 货币系统

传送门：https://www.luogu.org/problem/P5020

这题刚开始一眼暴力，按着题意来一遍，然后就在某谷AC了......

#include<cstdio>
#include<cstring>
#include<algorithm>
#define  R register
using namespace std;
int T,n,ans,a[110];
bool f[26000];
inline void init(){
    memset(f,0,sizeof(f));
    ans=0;
}
int main (){
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d",&n);
        for(R int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+1+n);
        for(R int i=1;i<=n;i++){
            if(!f[a[i]]) ans++,f[a[i]]=1;
            for(R int j=1;j<=a[n];j++){
                if(!f[j]) continue;
                if(j+a[i]<=a[n]){
                    if(!f[j+a[i]]) f[j+a[i]]=1;
                }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}