基本思路：
- 由于要求两个货币系统"等价"，换句话说，就是同时继承"优点"和缺点.
- 在此基础上，要使得货币量尽量小，就等于是在原货币系统中删去一些没用的货币（比如：3和6能组成9 12 15等）.
注意点：
- coins[i]（每种货币的价值）在预处理时需要排序.
- 需要判定价值是否超过coins[n]以免越界.
- 对于每组数据都要清空数组.
#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
",ans);
}
return 0;
}