记录编号	527440	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]货币系统	最终得分	100
用户昵称	HZOI_RXR	是否通过	通过
代码语言	C++	运行时间	0.182 s
提交时间	2019-02-16 14:29:42	内存使用	3.29 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int T,n,a[150],f[35000];
void work()
{
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	cin>>n;
	int ans=a[n];
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		if(!f[a[i]])
	   {
		   ans++;
	   f[a[i]]=1;
	   for(int j=a[i];j<=a[n];j++)f[j]|=f[j-a[i]];
       }
	}
	cout<<ans<<endl;
	
	
}
int main()
{
	freopen("2018money.in","r",stdin);
	freopen("2018money.out","w",stdout);
	
	cin>>T;
	while(T--)work();
}