代码

#include <bits/stdc++.h>
using namespace std;

#define MAXN 120
#define MAXV 25050
int a[MAXN], n, ans, ri[MAXV];
bool e[MAXN], isc[MAXV], v[MAXV];

//void euclid(int a, int b, int& d, int& x, int& y) {
//	if (b) {
//		euclid(b, a % b, d, y, x);
//		y -= x * (a / b);
//	} else {
//		d = a; x = 1; y = 0;
//	}
//}

//// returns if equation mx + ny = l has nonnegative integer solution
//bool iscomposed(int m, int n, int l) {
//	int d, x, y;
//	euclid(m, n, d, x, y);
//	if (l % d) return false;
//	x *= l / d; y *= l / d;
////	cout << m << " * " << x << " + " << n << " * " << y << " = " << l << endl;
////	cout << -x * d / n << " <= k <= " << y * d / m << endl;
////	return x * m + y * n >= 0;
//	return y * d / m > -x * d / n;
//}

bool iscg(int val, int ind) {
//	cout << "(" << val << ", " << ind << ")" << endl;
	if (val < a[0]) return false;
	if (ri[val] != -1 && ri[val] < ind) return true;
	if (v[val]) return isc[val];
	v[val] = true;
	for (int i = 0; i < ind; i++)
		if (/*val - a[i] >= a[0] && */iscg(val - a[i], ind)) return isc[val] = true;
	return isc[val] = false;
}

int main() {
	int t; cin >> t;
	while (t--) {
		memset(e, -1, sizeof(e));
		memset(v, 0, sizeof(v));
		memset(ri, -1, sizeof(ri));
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(a, a + n);	
		
		for (int i = 0; i < n; i++) {
			ri[a[i]] = i;
		}
			
		ans = n;
//		for (int i = 0; i < n; i++)
//			for (int j = 0; j < n; j++)
//				for (int k = 0; k < n; k++)
//					if (k != i && k != j && e[k] && e[i] && e[j] && iscomposed(a[i], a[j], a[k])) {
////						cout << a[i] << ", " << a[j] << " -> " << a[k] << endl;
//						e[k] = false;
//						ans--;
//					}

		v[a[0]] = true;
		isc[a[0]] = false;
		
		for (int i = 1; i < n; i++) {
			if (iscg(a[i], i)) //{
//				cout << "isc[" << a[i] << "] = " << 1 << endl;
				ans--;
//			} else
//				cout << "isc[" << a[i] << "] = " << isc[i] << endl;
		}
					
		cout << ans << endl;
	}
	
	return 0;
}

评测结果