嗯...

 

题目链接：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代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 int a[25005], f[25005]; 9 10 int main(){11     int t, n;12     scanf("%d", &t);13     for(int i = 1; i <= t; i++){14         memset(a, 0, sizeof(a));15         memset(f, 0, sizeof(f));16         f[0] = 1;17         scanf("%d", &n);18         int ans = n;19         for(int j = 1; j <= n; j++)20             scanf("%d", &a[j]);21         sort(a + 1, a + 1 + n);22         for(int j = 1; j <= n; j++){23             if(f[a[j]]) ans--;24             for(int k = a[j]; k <= a[n]; k++){25                 if(f[k] || f[k - a[j]]) f[k] = 1;//f[k] = f[k] | f[k - a[j]];26             }27         }28         printf("%d\n", ans);29     }30     return 0;31 }