牛客——货币系统（思维+DP）

牛客——货币系统（思维+DP）

题意：

求一个集合b，使得该集合能够表示出的数与给出的集合a能够表示出的数相同，输出该集合最少有多少个元素。

思路：

首先我们可以知道，如果集合里的一个数可以由集合里的其他数表示出来，那么前者就没有存在的必要了。

所以，在最优解里，集合b里面的元素一定是在集合a里的，因为只有这样，才能最小化集合b的元素个数。可以这样想，如果集合b里面的某个元素b[1]是由a[1] + a[2] 而来，而且a[1]、a[2]又可以由集合b的元素表示出来，那么b[1]的存在就没有意义了。

综上，可以从小到大排序后，判断a[i]能否被前面的数表示出来，如果可以的话，一定不选这个数；否则，一定要选这个数。之后借鉴完全背包的思想，进行状态转移，统计个数即可。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int>PII;

inline ll read(){
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

const int maxn=25100;

int n,a[maxn];
bool dp[maxn];

int main(){
    int t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        sort(a+1,a+1+n);
        memset(dp,0,sizeof dp);
        dp[0]=1;
        int res=0;
        for(int i=1;i<=n;i++){
            if(!dp[a[i]]) res++;
            for(int j=a[i];j<=a[n];j++)
                dp[j]|=dp[j-a[i]];
        }
        cout<<res<<endl;
    }
    return 0;
}