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

题意：

有 $n$ 种面值的货币，第 $i$ 种货币面值为 $a_i$ 。
这组货币组成的货币系统定义为 $(n, a)$ 。
求与 $(n, a)$ 等价的货币系统 $(m, b)$ 中，最小的 $m$ 。

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

题解：

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

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

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

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;
}