Sgu/434

若有k个数和为0，则可用至多k − 1次操作使得其全部变为0

所以此题就是把N个数分成尽量多的部分，使得每个部分的和都是0。

F_S表示已选集合为S，最多能够将其分成多少组，使得至多一个组的和不为0（显然为G_S）。

显然最后答案为$N-F_{2^N-1}$

---

#include <stdio.h>
#include <string.h>
 
int a[21], b[2097152], f[2097152], g[2097152];
int n;
 
long i, j, k = 0, l;
 
inline void max(int *a, const int b) { if (*a < b) *a = b; }
int main() {
	scanf("%d", &n);
	for (i = 0; i < n; ++i) scanf("%d", a + i);
	for (i = 0; i < n; ++i) scanf("%ld", &j), k += (a[i] -= j);
	if (k) return puts("-1"), 0;
 
	for (i = 0, k = 1; i < n; ++i, k <<= 1) b[k] = i;
	for (g[0] = 0, i = 1; i < k; ++i) j = i & -i, g[i] = g[i ^ j] + a[b[j]];
	memset(f, 0, sizeof f);
	for (i = 1; i < k; ++i)
		for (j = i; j; j ^= l) l = j & -j, max(f + i, f[i ^ l] + (g[i] == a[b[l]]));
 
	printf("%d", n - f[k - 1]);
	return 0;
}