洛谷 P5020 货币系统

嗯...

 

题目链接：https://www.luogu.org/problem/P5020

题目简化：

给定一个货币系统，该货币系统中有n种不同面值的货币，第i种货币的面值是a_i，我们将这个货币系统记作（n，a）。定义一个面值x能被（n，a）表示，当且仅当存在一个非负整数序列t，满足：给定一个货币系统（n，a），求一个货币系统（m，b），使得（n，a）与（m，b）是等价的，且m尽可能小。

首先证明一个事实，最终求出的货币系统中的元素，一定出现在原来的货币系统中，也就是不存在原来货币系统之外的元素。 

证明：

那么显然的是，最终我们求得到的集合就是（n，a）中不能被其他数字表示的数的集合。并且我们发现，如果一个数能被表示，那么显然会被比它小的数表示。

 

思路：

所以我们可以把原来的货币按照面值升序排序，从小到大考虑每一个数，设f[i]为只用到当前考虑的数之前的数能否表述出数字i。那么对于当前数字，如果它能被前面的数表示，那么可以扔掉。否则，将它加入答案，并更新f数组（其实是一个类似背包的问题

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int a[25005], f[25005];

int main(){
    int t, n;
    scanf("%d", &t);
    for(int i = 1; i <= t; i++){
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));
        f[0] = 1;
        scanf("%d", &n);
        int ans = n;
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[j]);
        sort(a + 1, a + 1 + n);
        for(int j = 1; j <= n; j++){
            if(f[a[j]]) ans--;
            for(int k = a[j]; k <= a[n]; k++){
                if(f[k] || f[k - a[j]]) f[k] = 1;//f[k] = f[k] | f[k - a[j]];
            }
        }
        printf("%d
", ans);
    }
    return 0;
}