货币系统

读完题目之后,内心一片祥和,除了想口吐芬芳........
题意:给定n个数,然后问最后剩余多少个数的时候,还可以把原来的数全部表示出来
举个例子:3 10 19 ,最后剩下2个数3和10即可,因为19=3+3+3+10
题解看一波范围,额,有点小.....最多才
那还想啥,直接暴力
比如3 可以构成3 6 9 12 15......
然后10可以构成10 20 30 40......
然后3和10结合可以构成13 16 19 22 25.....23 26 29 32 35......33.....
然后19,可以由前面比较小的两个数构成,n--
先排下序,然后对于然后判断当前数字是否可以由比他小的前面的数构成,如果当前的数在输入的n个数中,且可以由比其小的数构成n--

#include<bits/stdc++.h>
using namespace std;
int n,a[101],ans;
bool f[25001];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d",&n);
        ans=n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(f[a[i]]){ans--;continue;}
            for(int j=a[i];j<=a[n];j++)f[j]|=f[j-a[i]];
        }
        printf("%d\n",ans);
    }
}