P5020 货币系统

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
const int MAXN=2e3,MAXVALUE=5e4;
int coins[MAXN];
int vis[MAXVALUE];//该种价值是否能被组成 0:不能 1:能被组成 2:仅能被原始货币组成 
void init(){
	memset(vis,0,sizeof(vis));
	memset(coins,0,sizeof(coins));
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
        int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&coins[i]);//读入每种货币 
			vis[coins[i]]=2;//设置原始vis 
		}
		sort(coins+1,coins+n+1);//按价值从小到大排序
		for(int i=1;i<=coins[n];i++){//枚举每一种基础价格 
			if(vis[i]){//如果该价格能被组成 
				for(int j=1;j<=n;j++){//枚举每一种基础货币
					if(i+coins[j]>coins[n])break; 
					vis[i+coins[j]]=1;//设为能被组成 
				}
			}
			
		}
		int ans=0;
		for(int i=1;i<=coins[n];i++)
			if(vis[i]==2)ans++; 
		printf("%d\n",ans);
	}
	return 0;
}