POJ 1011: Sticks

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <string>

int first (int A[], int B[], int size) {
	for (int i = 1; i <= size; ++ i) {
		if (B[i] == 0) {
			B[i] = 1;
			return i;
		}
	}
	return 0;
}

int find (int A[], int B[], int size, int groupnum, int ith, int sum) {
	if (groupnum == ith) {
		return 1;
	}
	for (int i = 1; i <= size; ++ i) {
		if (B[i] == 0 && (sum + A[i]) < A[0]) {
			B[i] = 1;
			if (find (A, B, size, groupnum, ith, sum + A[i]))
				return 1;
			else
				B[i] = 0;
		}
		if (B[i] == 0 && (sum + A[i]) == A[0]) {
			B[i] = 1;
			int t = first(A, B, size);
			if (find (A, B, size, groupnum, ith + 1, A[t]))
				return 1;
			else {
				B[i] = 0;
				B[t] = 0;
				return 0;
			}

		}
		if (sum == A[0]) {
			int t = first(A, B, size);
			if (find(A, B, size, groupnum, ith + 1, A[t]))
				return 1;
			else {
				B[t] = 0;
				return 0;
			}
		}
	}
	return 0;
}

int go(int A[], int B[], int size, int groupnum) {
	return 0;
}

void swap (int &a, int &b) {
	if (a == b) return;
	a ^= b ^= a ^= b;
}

int partition (int A[], int p, int r) {
	int q = p;
	for (int i = p + 1; i <= r; ++ i) {
		if (A[i] > A[p]) {
			++ q;
			swap (A[q], A[i]);
		}
	}
	swap(A[q], A[p]);
	return q;
}

void qsort (int A[], int p, int r) {
	while (p < r) {
		int q = partition(A, p, r);
		qsort(A, p, q - 1);
		p = q + 1;
	}
}


int main () {
	int n = 0;
	scanf ("%d", &n);
	while (n) {
		int A[n + 1];
		int B[n + 1];
		memset (B, 0, sizeof (B));
		int sum = 0;
		for (int i = 1; i <= n; ++ i) {
			scanf ("%d", &A[i]);
			sum += A[i];
		}
		qsort (A, 1, n);
		for (int i = sum / A[1]; i >= 1; -- i) {
			if (sum % i == 0) {
				memset(B, 0, sizeof(B));
				A[0] = sum / i;
				if ( find(A, B, n, i, 1, A[first(A, B, n)]) ) {printf("%d\n", A[0]);
					break;
				}
			}
		}
		scanf ("%d", &n);
	}
	return 0;
}

经典深搜+剪枝

简单来讲就是穷举，但有很多地方可以优化。

1：只需考虑1到(sum / max)个组（循环是反过来写的，因为要求最短）

2: 进行排序

3： 假如有n个组，搜完n-1个组就可以了

。。。