NOIP2018 货币系统

货币系统

简单分析一下，不难得出结论：
m最小时，相当于把A系统简化，除去可以被A中其他元素组合的多余元素。
接下来是重点！！
若有一个数s能被之前的数a_i表示出来，那么(s - a_i)也能被之前的数表示出来
所以我们用\(f[i]\)表示\(i\)能否被表示出来。
我们定义边界\(f[0] = 1\)
每次把处理到的\(a[i]\)标记，然后筛除比a[i]大的那些可表示为\(a[i] + a[k]\ (0 < k < i)\)的数

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int T, n, a[25005], dp[25005], ans = 0;
int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int main(){
    cin >> T;
    while(T--){
        memset(a, 0, sizeof a);
        memset(dp, 0, sizeof dp);
        n = read(), ans = n;
        for(int i = 1; i <= n; i++)
            a[i] = read();
        sort(a + 1, a + n + 1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            if(dp[a[i]]){
                ans--;
                continue;
            }
            for(int j = a[i]; j <= a[n]; j++)
                dp[j] |= dp[j - a[i]];
        }
        cout << ans <<"\n";
    }
    return 0;
}