洛谷 P5020 货币系统

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 int a[25005], f[25005];
 9 
10 int main(){
11     int t, n;
12     scanf("%d", &t);
13     for(int i = 1; i <= t; i++){
14         memset(a, 0, sizeof(a));
15         memset(f, 0, sizeof(f));
16         f[0] = 1;
17         scanf("%d", &n);
18         int ans = n;
19         for(int j = 1; j <= n; j++)
20             scanf("%d", &a[j]);
21         sort(a + 1, a + 1 + n);
22         for(int j = 1; j <= n; j++){
23             if(f[a[j]]) ans--;
24             for(int k = a[j]; k <= a[n]; k++){
25                 if(f[k] || f[k - a[j]]) f[k] = 1;//f[k] = f[k] | f[k - a[j]];
26             }
27         }
28         printf("%d\n", ans);
29     }
30     return 0;
31 }