AcWing 532. 货币系统
原题链接
中等
作者:
黑夜最相似
,
2021-02-09 21:07:15
,
所有人可见
,
阅读 281
/*
对于货币系统(n, a):
性质1:一定能表示a[1...n];
性质2:如果a[1...n] 中a[i] 可以被其它数表示,他可以被删掉
性质3:对于等价的(m, b), b[1...m] 一定是 a[1...n] 中的数;
性质3:(n, b) 与 (m, b) 等价, 则 b[k] 一定能被 a[1...n] 表示出来,反之亦然
如果b[1...m] 不能表示 a[1...n]中的任意一个,那它们是不等价的(定义),性质3成立
反证法:假设b[k] 不是 a[1...n] 中的任意一个元素, 而 b[k] 可以被 a[1...n] 表示,
那么任意 b[k] > a[i], 即b[k] 不为a[1...n] 任意一个数
同理任意 a[i] 也可以被 b[1...m] 表示,则 b[k] 可以被b[1...m] 中的数表示出来
所以它是冗余的
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 25010;
int a[N];
int f[M];
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
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 res = 0;
for(int i = 0; i < n; ++i)
{
if(!f[a[i]]) res++;
for(int j = a[i]; j <= m; ++j)
f[j] += f[j - a[i]];
}
cout << res << endl;
}
return 0;
}