程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SRM 622 D2L3: Subsets, math, backtrack

SRM 622 D2L3: Subsets, math, backtrack

編輯：C++入門知識

符合條件的集中非1的元素個數是很少的，可以用回溯加剪枝，實際運行速度很快。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define CHECKTIME() printf(%.2lf
, (double)clock() / CLOCKS_PER_SEC)
typedef pair pii;
typedef long long llong;
typedef pair 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  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  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 ************************/