思路

用is[x]表示x是否能被其他货币表示出来
再把a中能被其他货币加起来表示的除去
剩下的数量就是答案

实现

用两个集合,一个集合放a,另一个集合表示是否能被其他货币表示

状态转移

对于每一个ai,从ai+1开始到max判断是否能被表示,可从is[i]和a中是否存在i进行状态转移,如果is[i]为true或者a中有i,则is[ai+i]为true

可以发现a集合很适合用HashSet进行表示

核心代码

        for (int x : a)
            for (int i = x + 1; i <= max; i++) {
                int p = i - x;
                if (set.contains(p) || is[p]) is[i] = true;
            }

(完全背包) $O(n*m)$

m为a中的最大值

主要Code

        int n = nextInt(), max = 0;
        int[] a = new int[n];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
            set.add(a[i]);
            max = Math.max(max, a[i]);
        }
        boolean[] is = new boolean[max + 1];
        is[0] = true;
        for (int x : a)
            for (int i = x + 1; i <= max; i++) {
                int p = i - x;
                if (set.contains(p) || is[p]) is[i] = true;
            }
        for (int s : set) if (is[s]) n--;
        out.write(n + "\n");

完整代码(包括快读快写)

import java.io.*;
import java.util.*;

public class Main {

//    static final File file = new File("./TestCase/in.txt");
//    static BufferedReader reader;
//
//    static {
//        try {
//            reader = new BufferedReader(new FileReader(file));
//        } catch (FileNotFoundException e) {
//            throw new RuntimeException(e);
//        }
//    }

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(reader);
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
//    static StringTokenizer in = new StringTokenizer(reader);

    static String next() {
        try {
            in.nextToken();
            return in.sval;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    static double nextDouble() {
        try {
            in.nextToken();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return in.nval;
    }

    static int nextInt() {
        return (int) nextDouble();
    }

    static void solve() throws IOException {
        int n = nextInt(), max = 0;
        int[] a = new int[n];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
            set.add(a[i]);
            max = Math.max(max, a[i]);
        }
        boolean[] is = new boolean[max + 1];
        is[0] = true;
        for (int x : a)
            for (int i = x + 1; i <= max; i++) {
                int p = i - x;
                if (set.contains(p) || is[p]) is[i] = true;
            }
        for (int s : set) if (is[s]) n--;
        out.write(n + "\n");
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        while (n-- > 0)
            solve();
        out.flush();
        out.close();
    }
}