P5020 [NOIP2018 提高组] 货币系统

【传送门】[NOIP2018 提高组] 货币系统 - 洛谷

（n，a）系统和（m，b）系统等价，即（n，a）系统中可以组成的面值和（m，b）一模一样，也就是说当a[]数组中所有的值，都可以用b[]数组中的面值表示出来。

怎么得到b[]数组呢？

a[]中最小值x肯定与b[]中最小值相同，所以x加入b[]中，然后看a[]中次小y，能不能用x组成，若不能，加入y，差不多这样循环下去。

看下数据规模，就是背包dp

具体解释看代码：

#include
using namespace std;

const int maxn = 3e4;
int a[105];
bool c[maxn];
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        int mx = a[n]; //我们只要判断到mx即可
        c[0] = true;//初始化
        for(int i = 1; i <= mx; i++){
            c[i] = false;
        }
        int cnt = 0;
        for(int i = 1; i <= n; i++){ //n张面值
            bool fg = false;//判断是否需要加入
            for(int j = a[i]; j <= mx; j++){
                if(c[j]) continue;//如果已经可以通过前面面值合成
                if(!c[j - a[i]]) continue; //如果减去该面值，前面金额无法合成
                c[j] = true;//否则加入a[i]，j金额可以合成
                fg = true;//需要加入
            }
            if(fg) cnt++;
        }
        cout << cnt << "n";
    }
}