世界冰球锦标赛(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))
