N0lP 2018 貨幣系統

N0lP 2018 貨幣系統#

~~划水一周就寫了個這玩意兒？~~

題目#

傳送門

貨幣種數為 $n$、面額陣列為 $a [1..n]$ 的貨幣系統記作 $(n,a)$。

兩個貨幣系統 $ (n,a)$ 和 $ (m,b)$ 是等價的，當且僅當對於任意非負整數 $x$，它要麼均可以被兩個貨幣系統表出，要麼不能被其中任何一個表出。

找到一個貨幣系統 $(m,b)$，滿足 $(m,b)$ 與原來的貨幣系統 $(n,a)$ 等價，且 $m$ 盡可能的小。

輸出最小的 $m$

解法#

如果一個貨幣系統裡的某些貨幣能被另一些貨幣表示，那麼就可以踢掉。

所以，先排序，然後對每一個a[i]，把它標記為可以被表示，

再利用完全背包的思想來篩（把能被填滿的貨幣標記）

Code#

#include <cstdio>
#include <algorithm>

using std::max;
using std::sort;

const int MAXN = 105, MAXA = 25000;

int main (void) {
    int T;
    scanf("%d", &T);
    while (T--) {
        int a[MAXN] = {0};
        bool v[MAXA] = {0};
        int n, maxa = 0, ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            maxa = max(maxa, a[i]);
        }
        sort(a + 1, a + 1 + n);
        for (int i = 1; i <= n; ++i) {
            if (v[a[i]]) continue;
            ++ans;
            v[a[i]] = 1;
            for (int j = a[i]; j <= maxa; ++j) {
                if (v[j - a[i]]) v[j] = 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}