世界冰球锦标赛(day2)(这只是一道题)

链接

这道题本质上还是找子序列问题,需要递归

但是由于数据很大,足足有40个达2^40,绝对会超时,所以我们需要用别的方法来简化

此题用到的是折半搜索,我们将40个分成前后两半,这样就是2*2^20, 少了很多

代码如下

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
void f(int start, int end, ll current_sum, ll m, vector<ll>& sum, vector<ll>&nums) {
	if (start > end) {
		sum.push_back(current_sum);
		return;
	}

	f(start + 1, end, current_sum, m, sum,nums);

	if (current_sum + nums[start] <= m) {
		f(start + 1, end, current_sum + nums[start], m, sum, nums);
	}
}
int main() {
	ll n, m;
	cin >> n >> m;
	vector<ll>nums(n);
	for (int i = 0;i < n;i++) {
		cin >> nums[i];
	}
	vector<ll>sums_fir, sums_sec;
	int mid = n / 2;
	f(0, mid-1, 0, m, sums_fir, nums);
	f(mid ,n-1, 0, m, sums_sec, nums);
	ll count = 0;
	sort(sums_sec.begin(), sums_sec.end());
	for (ll number : sums_fir) {
		ll remain = m - number;
		auto it = upper_bound(sums_sec.begin(), sums_sec.end(), remain);
		count += it - sums_sec.begin();
	}
	cout << count;
}

递归时候,是从后往前,将所有可能数据遍历一遍 时间复杂度:O(n^(n/2))

空间复杂度:O(2*2^(n/2))