[Time Gate] https://www.luogu.org/problem/P5020 【解题思路】 3 10 19 6等价于3 10 这是因为 19=10+3+3+3 6=3+3 看起来我们要把能够被其他钱 凑 出来的数给筛掉，这样一来剩下的就是我们必须要保留的面
[Time Gate]
https://www.luogu.org/problem/P5020
【解题思路】
3 10 19 6等价于3 10
这是因为19=10+3+3+3 6=3+3
看起来我们要把能够被其他钱凑出来的数给筛掉，这样一来剩下的就是我们必须要保留的面值了
那我们可以建一个数组mon[i]，来存面值为i的钱能不能被其它面值的钱凑出来
最后再把整个mon跑一遍，看看原货币系统中剩下几个不能被凑出来的钱，这就是答案了
【code】
1 #include <cstdlib>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std; 6 int mon[25001]={}; 7 /*
8 mon[i]=0 表示i面值的钱不能被凑出来 9 mon[i]=1 表示i面值的钱可以被凑出来 10 mon[i]=2 表示i面值的钱是货币系统中本来就有的钱 11 */
12 int coins[101]={};//存钱的面值
13 int T,n,ans=0; 14 int main() 15 { 16 scanf("%d ",&T); 17 while (T--) 18 { 19 ans=0; 20 memset(mon,0,sizeof(mon)); 21 memset(coins,0,sizeof(coins)); 22 scanf("%d",&n); 23 for (int i=1;i<=n;i++) 24 { 25 scanf("%d",&coins[i]); 26 mon[coins[i]]=2; 27 } 28 //把货币系统中的钱标好
29 sort(coins+1,coins+1+n); 30 for (int i=1;i<=coins[n];i++) 31 { 32 if (mon[i]>0) 33 //如果mon[i]能被凑出来 34 //那么mon[i+coins[j]]也能被凑出来
35 { 36 for (int j=1;j<=n;j++) 37 if (i+coins[j]<=coins[n]) 38 //防止数组越界
39 mon[i+coins[j]]=1; 40 else break; 41 } 42 } 43 for (int i=1;i<=coins[n];i++) 44 if (mon[i]==2) ans++; 45 printf("%d\n",ans); 46 } 47 }