题目链接 AcWing 532.货币系统
思路
- 对a[i]进行排序
- 对于任意一个数 $a_i$ ,判断 a1, a2, a3 .... $a_{i-1}$ 是否能凑出 a[i] 即 f[a[i]] 方案数是否 > 0
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 25010;
int n;
int f[M];
int a[N];
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n);
int m = a[n - 1]; //最大值
memset(f, 0, sizeof f);
f[0] = 1;
int ans = 0; //答案
for (int i = 0; i < n; i ++ ) //完全背包问题
{
if(!f[a[i]]) ans ++; //不存在
for(int j = a[i]; j <= m; j ++)
f[j] += f[j - a[i]];
}
cout << ans << endl;
}
return 0;
}