noip2018 洛谷 P5020 货币系统

关键： 要使m最小，(m,b)中的数不能用（n,a）中的数表示出来

对于 3  19  10  6

19=10+3+3+3

6=3+3

只有3 和 10 不能被（n，a）中的数表示

所以m=2

只需要计算出存在多少个能被其它数组成的数计算出来就行了。

法一：完全背包

一个数只能被比它小的数字组成而不能被比它大的数字组成。

可以首先对数组排序，然后对于每一个数考虑能不能被它前面的数字所组成。

若x能够被前i个数组成，那么x-a[i]也能被前i个数组成

f[x]表示x能否被组成

则f [ x ] = f [ x ]  |  f [ x – a [ i ] ]

 #include<bits/stdc++.h>
 using namespace std;
 const int maxn=;
 int main()
 {
     int a[maxn];
     int f[maxn];
     int t,n;
     int ans;
     cin>>t;
 while(t--){
       memset(f,,sizeof(f));
       cin>>n;
       ans=n;
       for(int i=;i<=n;i++)
         cin>>a[i];
       sort(a+,a+n+);
         f[]=; //边界
       for(int i=;i<=n;i++)
       {
           if(f[a[i]])//a[i]能被前面的数表示
           {
           ans--;
           continue;
         }
         for(int j=a[i];j<=a[n];j++)
             f[j]= (f[j]) | (f[j-a[i]]);
       }
       cout<<ans<<endl;
 }
 return ;
 }