[数据结构与算法]货币系统（偏数学）

货币系统
大意就是，给你一组数，让你求另一组数，要求可以用给定组的数表示出来的数，都可以被你求的组里面的数表示出来。问你求出来的组里面的数最少有几个。

有几个很显然的性质，不明白扽可以去看看Y总的课

先给给定的数组排个序，因为小的可以表示大的，但是大的不能表示小的。因此对于每个数，就看一看它前面的数能不能表示出来它就好。至于怎么求能不能表示，就是一个完全背包，看看是不是体积是ai的可以被前面体积是$a_1$ ~ $a_{i?1}$的恰好装满

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 110, M = 25010;

int n;
int a[N], f[M];

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i=1; i<=n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        int m = a[n];
        
        memset(f, 0, sizeof f);
        f[0] = 1;
        
        int res = 0;
        for(int i=1; i<=n; i++)
        {
            if(!f[a[i]]) res++;//a[i]不能被之前的数恰好表示出来
            for (int j = a[i]; j <=m ; j ++ )//用a[i]表示其他数试试
            {
                f[j] += f[j - a[i]];
            }
        }
        
        cout << res << endl;
    }
    
    return 0;
}

//53：00

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖