N0lP 2018 Currency System

N0lP 2018 Currency System#

~~Took a week off and wrote this thing?~~

Problem#

The currency system with the number of currencies as $n$ and the denomination array as $a[1..n]$ is denoted as $(n,a)$.

Two currency systems $(n,a)$ and $(m,b)$ are equivalent if and only if for any non-negative integer $x$, it can either be represented by both currency systems or by none of them.

Find a currency system $(m,b)$ that is equivalent to the original currency system $(n,a)$, and $m$ is as small as possible.

Output the minimum value of $m$.

Solution#

If some currencies in a currency system can be represented by other currencies, they can be removed.

Therefore, sort first, then for each a[i], mark it as representable,

then use the idea of complete backpack to filter (mark the currencies that can be filled)

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