货币系统题解

先拿到这个题，我看到多组数据，就认为是要进行一些神奇的预处理，然后输入输出就好，但这道题的每个样例都告诉我，每组货币之间没有联系，因为存在大数可以被之前的小数替代的可能，被原货币系统的替代更保险，所以就感觉预处理走不通

题目要求的是找到可以替换掉当前数组的最短数组，刚开始，我想的是把所有的数分解开来，但分解后会产生可以组合成的新数，所以又想到了排除当前货币里的冗余货币，就是大的谁能被小的组成，谁就不可以，而且每种货币没有限制，所以就是完全背包问题。

然后按照贪心的想法，小的能组成的是比大的多的，所以小的应该尽可能留下，所以就排一下序，同时，如果最后最少的货币系统里有比原货币系统最大的也不行，所以背包最大值应该就是原货币系统的最大值

code

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,m;    
    int a[110];//存初始的货币
    //int v[25010];//记录每个数是否可以被组成
    int main()
    {
        int T;
        cin>>T;
        while(T--)
        {
            cin>>n;
            bool v[25010]={false};
            for(int i=1;i<=n;i++)
              cin>>a[i];
            m=0;
            sort(a+1,a+1+n);//必须排序
            for(int i=1;i<=n;i++)
            {
                if(v[a[i]]) continue;//当前的可以被之前的组合出来所以跳过
                m++;//不能的话就选上这个
                v[a[i]]=1;
                for(int j=a[i];j<=a[n];j++)
                {
                    if(v[j-a[i]]) v[j]=1;
                }
           }
          cout<<m<<endl;
        }
        return 0;
    }

PS：~~当然就是题解，我原来不会~~

这要是看出来是个背包，我也不至于....

P5020 货币系统

货币系统题解

code

讲题的感觉