【每日一题】 货币系统

题目描述
在网友的国度***有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。
在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。
两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b) 与原来的货币系统(n,a)等价，且m尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。

输入描述:
输入的第一行包含一个整数T,表示数据组数。接下来按照如下格式分别给出T组数据。
每组数据的第一行包含一个正整数n。接下来一行包含n个由空格隔开的正整数a[i]。

输出描述:
输出文件共T行, 对于每组数据, 输出一行一个正整数, 表示所有与(n, a)等价的货币系统(m, b)中, 最小的m。

题解
题目的意思就是给定一个包含n个元素的集合A，求一个最小的子集B使得A能表示的数B也能表示，A不能表示的数B也不能表示，我们可以发现，因为B是A的子集，所以A不能表示的数B一定不能表示，因此我们只需要处理能表示的数就可以。再仔细想一下，其实这道题就是让我们求这个集合里哪些元素不可以被集合里的其他元素表示，比如样例的集合{3，19，10，6}，如果一个元素可以被其他元素代替，那么这个元素可以表示的不属于这个集合的元素也可以被表示出来，比如12=6+6，而6=3+3，所以我们没必要保留6，想通以后就很容易发现这是一道完全背包求方案数的题，只不过需要先从小到大排序一遍。
代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 3e4+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}

int v[N],a[101];
void solve(){
    memset(v,0,sizeof(v));
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int ans=0;
    v[0]=1;
    for(int i=1;i<=n;i++){
        if(!v[a[i]]){
            ans++;
            for(int j=a[i];j<=a[n];j++){
                v[j]|=v[j-a[i]];
            }
        }
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve(),cout<<'\n';
    //solve();
    return 0;
}