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] を表現可能としてマークする。

その後、完全バックパックの考え方を利用してフィルタリングする（満たすことができる通貨をマークする）。

コード#

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