P5020 [NOIP2018 提高组] 货币系统-526互联

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
const int A = 25005;
int a[N];
bool dp[A];
int main()
{
	int t; scanf("%d", &t);
	while (t--) {
		int n; scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]); 
		}
		sort(a + 1, a + n + 1);
		for (int i = 1; i <= a[n]; i++) dp[i] = false;
		dp[0] = true;
		int ans = n;
		for (int i = 1; i <= n; i++) {
			if (dp[a[i]]) {
				ans--; continue;
			}
			for (int j = a[i]; j <= a[n]; j++)
				dp[j] |= dp[j - a[i]];
		}
		printf("%d\n", ans);
	}
	return 0;
}