P4799世界冰球锦标赛洛谷

冰球锦标赛洛谷"/>

P4799世界冰球锦标赛洛谷

完整AC代码,注释很详细
 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, nums[45];
ll ans;//答案个数
ll p[1 << 21];//可能性 这是一半的所有可能情况,爆搜极限是2 ^ 40,一半就是2 ^ 20,多给点空间
ll k;//一半n / 2
ll cnt;//记录p有多少个
void ldfs(ll index, ll s) {if (index == k) {//到一半的头了,记录当前数p[cnt++] = s;return;}//这个门票就两种情况,选还不是不选ldfs(index + 1, s);//不选if (s + nums[index] <= m) ldfs(index + 1, s + nums[index]);//选的情况得if判断,不能超过限定的金额
}
void rdfs(ll index,ll s) {if (index == n) {//又到一半的头了//s + a <= m 这就是当前符合情况的门票数 那这个a <= m - s 此时用upper找这个,同时,所以,前面ldfs搜完得对p数组排序的auto it = upper_bound(p, p + cnt, m - s) - p;ans += it;//拿到结果return;}//还是选或者不选rdfs(index + 1, s);//不选if (s + nums[index] <= m) rdfs(index + 1, s + nums[index]);//和ldfs一样的思路
}
int main() {ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);cin >> n >> m;//下面预处理的是用点技巧,稍微剪剪枝int j = 0;//数组中真正数字的个数for (int i = 0; i < n; ++i) {cin >> nums[j];//注意,是j不是iif (nums[j] <= m)++j;//只有当前输入的这个数小于等于m才记入数组,不然压根不放进去,不过这里也不是完全意义上的不放进去//因为比如最后一个大于了,j不变,但是for循环已经结束,这样还是放进去了,但是,注意,后面n的修改还是依据j,它虽然放进去了//但是也是压根不会遍历到的!!!}n = j;//变换nsort(nums, nums + n, greater<ll>());//从大到小,这样也能加快点速度k = n / 2;//拿到真正数组个数的一半//以上就是预处理的全部过程ldfs(0, 0);//拿到p数组得排序,不然后序的upper没法用sort(p, p + cnt);rdfs(k, 0);cout << ans << endl;
}