考察点

完全背包的变种

题目分析

若 一种货币可以被其余货币表示出来，则该货币没有存在必要。
最后剩余 的货币种类数就是我们需要的答案

算法1

f[i][j]代表能否使用前i个数表示出来j，1 or 0 .先从小到大排一下序，若f[i-1][a[i]]==true 则a[i] 没有存在必要

C++ 代码

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

using namespace std;

const int N=110,M=25010;

int f[N][M];
int a[N];
int n;

int main(){
    int T;
    cin>>T;
    while(T--){
     memset(a,0,sizeof a);
     memset(f,0,sizeof f);
     int n;    
     cin>>n;    

     int res=n;
     for(int i=1;i<=n;i++) cin>>a[i];   
     sort(a+1,a+n+1);

     f[0][0]=1;
     for(int i=1;i<=n;i++)
      for(int j=0;j<=a[n];j++){
        f[i][j]=f[i-1][j]; 
        if(j>=a[i]) f[i][j]=f[i][j]||f[i][j-a[i]];     
      }

    for(int i=2;i<=n;i++)
     if(f[i-1][a[i]]) res--;

    cout<<res<<endl;
    }

    return 0;
}

算法2

f[i][j]代表方案数。若f[n][a[i]]>1,说明a[i]可以被其他数表示出来没有存在必要。但我们需要对数组a[]先去重，不然
的话，我们假设数组a[3]={1,1,1},我们会发现 a[0]、a[1]、a[2]都没有存在必要，这是错误的。

C++ 代码

#include<cstring>
#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N=25010; 

vector<int> a;
int f[N];
int n;

int main(){
   int T;
   cin>>T;
   while(T--){
      a.clear();
      memset(f,0,sizeof f);
      cin>>n; 
      a.push_back(0); 

      int maxm=-1;
      for(int i=1;i<=n;i++) {
          int x;
          cin>>x;
          maxm=max(maxm,x);
          a.push_back(x);
      }

     a.erase(unique(a.begin(),a.end()),a.end());   // 去重

     f[0]=1;  
     n=a.size()-1;
     for(int i=1;i<=n;i++)  
       for(int j=a[i];j<=maxm;j++)
        f[j]=f[j]+f[j-a[i]];


     int res=0;
     for(int i=1;i<=n;i++) if(f[a[i]]==1) res++;

     cout<<res<<endl;
   }

  return 0;
}