代码

#include <bits/stdc++.h>

constexpr int N = 100 + 5;

int a[N];
std::bitset<25005> f;

inline char nc()
{
	static char buf[1000000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read()
{
	int res = 0;
	char ch;
	do ch = nc(); while (ch < 48 or ch > 57);
	do res = res * 10 + ch - 48, ch = nc(); while (ch >= 48 && ch <= 57);
	return res;
}

int main()
{
	int T = read();
	while (T--)
	{
		int n = read(), ans = n;
		for (int i = 0; i < n; ++i) a[i] = read();
		std::sort(a, a + n);
		f.reset();
		f[0] = 1;
		for (int i = 0; i < n; ++i)
		{
			if (f[a[i]]) --ans;
			else
			{
				int bound = a[n - 1] / a[i];
				for (int j = 1; j <= bound; bound -= j, j <<= 1) f |= f << (j * a[i]);
				f |= f << (bound * a[i]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

评测结果