AcWing 532. 货币系统
原题链接
中等
作者:
小.bug
,
2022-05-14 13:59:53
,
所有人可见
,
阅读 131
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 25010;
int n, m, T;
int f[N][M];
int a[N];
int main()
{
cin >> T;
while(T -- )
{
int res = 0;
memset(f,0,sizeof f);
f[0][0] = 1;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1,a+1+n);
m = a[n];
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i-1][j];
if(j >= a[i])
f[i][j] += f[i][j-a[i]];
}
}
//因为a数组已经排好序
//如果a[i]不能用前i-1的面值凑出来,就需要保留
for(int i = 1; i <= n; i++)
{
if(!f[i-1][a[i]]) res ++;
}
cout << res << endl;
}
return 0;
}