Posted in DFS

PKU 24 Sticks

Problem: http://acmicpc.openjudge.cn/practice/024/


#include<iostream> 
#include<cstring>
#include<algorithm>
using namespace std;
int a[105] = {0};
bool v[105];
int sum = 0, m = 0, ans;
int len, num, n;

bool cmp(int x, int y) {
	return x > y; 
}

bool dfs(int stick, int l) {
	if (stick == num) {
		return true;
	}
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			if (l + a[i] > len) {
				continue;
			} else if (l + a[i] == len) {
				v[i] = true;
				bool b = dfs(stick + 1, 0);
				v[i] = false;
				return b;
			} else {
				v[i] = true;
				bool b = dfs(stick, l + a[i]);
				v[i] = false;
				if (b) {
					return true;
				} else if (!b && l == 0) {
					return false;
				}
			}
		}
	}
	return false;
}

int main() {
	while (cin >> n) {
		memset(v, false, sizeof(v));
		memset(a, 0, sizeof(a));
		sum = 0;
		m = 0;
		if (n == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum += a[i];
			if (a[i] > m) {
				m = a[i];
			}
		}
		sort(a + 1, a + n + 1, cmp);
		for (len = m; len <= sum; len++) {
			if (sum % len == 0) {
				num = sum / len;
				if (dfs(1, 0)) {
					cout << len << endl;
					break;
				}
			}
		}
	} 
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s