记录编号	540982	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]货币系统	最终得分	100
用户昵称	wire	是否通过	通过
代码语言	C++	运行时间	0.132 s
提交时间	2019-09-03 18:56:24	内存使用	13.75 MiB

#include<bits/stdc++.h>
#define M 25001
int T,n,ans=0;
int money[M]={},coin[101]={};
int main ()
{
	freopen("2018money.in","r",stdin);
	freopen("2018money.out","w",stdout);
	std::cin>>T;
	while(T--)
	{
		ans=0;
		memset(money,0,sizeof(money));
		memset(coin,0,sizeof(coin));
		std::cin>>n;
		for(int i=1;i<=n;i++)
		{
			std::cin>>coin[i];
			money[coin[i]]=2;
		}
		std::sort(coin+1,coin+1+n);
		for(int i=1;i<=coin[n];i++)
		{
			if(money[i]>0)
			{
				for(int j=1;j<=n;j++)
				{
					if(i+coin[j]<=coin[n])
					{
						money[i+coin[j]]=1;
					}
					else break;
				}
			}
		}
		for(int i=1;i<=coin[n];i++)
		{
			if(money[i]==2)
			{
				ans++;
			}
		}
		std::cout<<ans<<std::endl;
	}
}