SRM 622 D2L3: Subsets, math, backtrack

题目：http://community.topcoder.com/stat?c=problem_statement&pm=10554&rd=15855

符合条件的集中非1的元素个数是非常少的，能够用回溯加剪枝。实际执行速度非常快。

代码：

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;

#define CHECKTIME() printf("%.2lf
", (double)clock() / CLOCKS_PER_SEC)
typedef pair<int, int> pii;
typedef long long llong;
typedef pair<llong, llong> pll;
#define mkp make_pair
#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it)

/*************** Program Begin **********************/

class Subsets {
public:
	vector <int> numbers;
	int ones_cnt;
	int res;
	int nextdiff[1005];
	void backtrack(int sum, int prod, int pos)
	{
		// add
		int cur = numbers[pos];
		int next_sum = sum + cur;
		int next_prod = prod * cur;
		if (next_sum + ones_cnt > next_prod) {
			res += next_sum + ones_cnt - next_prod;
			if (pos + 1 < numbers.size()) {
				backtrack(next_sum, next_prod, pos + 1);
			}
		}

		// not add
		if (nextdiff[pos] < numbers.size()) {
			backtrack(sum, prod, nextdiff[pos]);
		}
	}

	int findSubset(vector <int> numbers) {
		sort(numbers.begin(), numbers.end());
		this->numbers = numbers;
		int n = numbers.size();

		for (int i = 0; i < n; i++) {
			nextdiff[i] = n;
			for (int j = i + 1; j < n; j++) {
				if (numbers[i] != numbers[j]) {
					nextdiff[i] = j;
					break;
				}
			}
		}
		
		ones_cnt = count(numbers.begin(), numbers.end(), 1);
		res = max(ones_cnt - 1, 0);
		if (ones_cnt < n) {
			backtrack(0, 1, ones_cnt);
		}

		return res;
	}

};

/************** Program End ************************/