【每日一题】【5月27日】货币系统

题意：

有 种面值的货币，第 种货币面值为 。
这组货币组成的货币系统定义为 。
求与 等价的货币系统 中，最小的 。

两个货币系统等价定义为：任意面额 ，要么均不能被两个货币系统表示出来，要么均能被表示出来。

题解：

考虑 中会存在哪些数：
考虑某个面额 ：
若 不能被表示出来，那么 中肯定没有这个元素。
若 能被表示出来，那么这个元素必然是由 中其它元素表示出来的，所以删掉也不影响系统的表示能力，而且货币数更少。

因此 中的元素必然是 的一个子集。
若 ：考虑 是否能由其它元素表示出来，若不能，那么 中必须要保留这个元素。若能，则可以去掉这个元素。

那么我们要做的就是考虑 中有哪些数可以有其它数表示出来。显然一个可以被其它数表示出来的值，必然大于这些数。
那么我们我们对 数组排序，然后从小到大跑一个完全背包，若 未被表示，则记入 即可。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 25000 + 5;
int a[N], f[N], n;
int main() {
    int T; cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        memset(f, 0, sizeof f);
        f[0] = 1;
        int ans = 0;
        for(int i = 1; i <= n; i++) if(!f[a[i]]) {
            ans++;
            for(int j = a[i]; j < N; j++) f[j] |= f[j - a[i]];
        }
        cout << ans << endl;
    }
    return 0;
}