【题解】货币系统

前言：

这个题就是完全背包的裸题，只要把题目完全读懂就好了，难度不高。

思路：

首先我们知道，题目的意思是说能不能用更少种类的钱来表示这个货币系统，换言之就是，有的钱它可能可以通过小面额的钱来组成，那这种钱就不需要存在这个货币系统了，比如：2 5 9这个9就可以通过2+2+5来组成，所以9这个面额就可以不需要了；但是2无法组成5，所以5这个面额是需要的。
所以题意就是在说：哪些面额的钱不能通过小面额的钱来组成
因此就很简单了，那只需要先排个序，从小面额开始跑完全背包，如果之后发现这个面额是可以通过小面额的钱组成的就跳过，统计一下答案就好了。

完全背包不用教了吧，大家百度一下完全背包就能理解了。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e5+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int dp[maxn];
int a[maxn];

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        sort(a+1,a+1+n);
        int ans=0;
        dp[0]=1;
        for(int i=1;i<=n;i++){
            if(!dp[a[i]]){
                ans++;
                for(int j=a[i];j<maxn;j++){
                    dp[j]|=dp[j-a[i]];
                }
            }
        }
        printf("%d\n",ans);
        memset(dp,0,sizeof(dp));
    }
    return 0;
}