NC21228 [NOIP2018]货币系统（背包）

题意

组数据，有 种货币，每种货币有无限量，求最少的货币种类，使得所有种类的货币可以被表示。 。

分析

先将货币数值排序，如果 可以被前面的表示，那么 显然没用了。如果没被表示，就显然必须加入货币系统。
怎么看能不能被表示呢？这不就是个背包吗=。=
复杂度

代码如下

#include <bits/stdc++.h>
#define N 105
using namespace std;
typedef long long LL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int a[N], f[25005];
int main(){
    int i, j, n, m, T, ans;
    T = read();
    while(T--){
        n = read();
        for(i = 1; i <= n; i++) a[i] = read();
        sort(a + 1, a + i);
        memset(f, 0, sizeof(f));
        f[0] = 1; ans = 0;
        for(i = 1; i <= n; i++){
            if(f[a[i]]) continue;
            ans++;
            for(j = a[i]; j <= 25000; j++) f[j] |= f[j - a[i]];
        }
        printf("%d\n", ans);
    }
    return 0;
}