AcWing 532. 货币系统

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25010;
int n;
int a[N];
bool f[N];
int main() {
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        for (int i = 0; i < n; i ++ )
            cin >> a[i];
        sort(a, a + n);//货币从小到大排序
        int m = a[n - 1];//取最后一个货币 ，也就是最大体积
        memset(f, 0, sizeof f);
        f[0] = true;
        int k = 0;
        for (int i = 0; i < n; i ++ ) {
            if (!f[a[i]])//从小开始看，如果没有拼凑方案 
                k ++ ;
            for (int j = a[i]; j <= m; j ++ )
                f[j] += f[j - a[i]];
        }

        cout << k << endl;
    }

    return 0;
}