1014.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream>
#define n 6
using namespace std;

int rock[7], mid , r;
bool print, opt[60001];

void init() {
	int i;
	mid = 0;
	print = true;
	for (i=1; i<=n; i++) {
		cin >> rock[i];
		mid = mid + rock[i] * i;
		if (rock[i] % 2 == 1)
			print =  false;
	}
}

void dp() {
	int max, i, j, k;
	memset(opt, false, sizeof(bool) * 60001);
	/*for (i=0; i<60001; i++) {
		opt[i] = false;
	}*/
	opt[0] = true;
	max = 0;
	print = true;
	for (i=1; i<=n; i++) {
		if (rock[i] > 0) {
			for (j=max; j>=0; j--) {
				if (opt[j]) {
					if (opt[mid]) {
						print = true;
						cout << "Can be divided." << endl;
						return ;
					}
					for (k=1; k<=rock[i]; k++) {
						if (j+k*i > mid || opt[j+k*i])
							break;
						opt[j+k*i] = true;
					}
				}
			}
		}
		max = max + i * rock[i];
		if (max > mid) {
			max = mid;
		}
	}
	print = false;
}

int main() {
	init();
	r = 0;
	while (mid != 0) {
		r ++;
		cout << "Collection #" << r << ":" << endl;
		if (mid % 2 == 0 && !print) {
			mid = mid / 2;
			dp();
			if (!print)
				cout << "Can't be divided." << endl;
		}
		else {
							cout << "Can't be divided." << endl;
		}
		cout << endl;
		init();
	}

	return 0;
}