?
符合条件的集中非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 ************************/