P5020 货币系统

题面:https://www.luogu.org/problem/P5020

本题如果a数组中有一个数可以被其它数表示出来,那么就可以不选它,然后就变成了完全背包裸题.

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
using namespace std;
const int N=105,M=25000;
int t,n,a[N],f[M+10];
int main(){
    scanf("%d",&t);
    while(t--){
        int ans=0;
        memset(f,-63,sizeof(f));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        f[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=a[i];j<=M;j++){
                f[j]=max(f[j],f[j-a[i]]+1);
            }
        }
        for(int i=1;i<=n;i++){
            if(f[a[i]]==1){
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}