#include"bits/stdc++.h"usingnamespacestd;usingu32=uint32_t;usingu64=uint64_t;u32n;u64k;vector<u32>a;u64ans_cnt{};constexprautokOverflow=numeric_limits<u64>::max();// an arbitrary (but larger than `kThreshold`) number to indicate overflowconstexpru64kThreshold=20000000;// returns `found_answer`booldfs(u32pos,u64accum){if(accum>k){// a[pos] has not been taken into accountu32nums_left=n-pos;if(nums_left>=25){ans_cnt=kOverflow;}else{ans_cnt+=(u64)1<<nums_left;if(ans_cnt>kThreshold){ans_cnt=kOverflow;}}returntrue;}if(pos==n){returnfalse;}autofound_answer=dfs(pos+1,accum+a[pos]);if(!found_answer){returnfound_answer;}// if no answer even if we take everything we can, then there's no hope.if(ans_cnt==kOverflow){returntrue;}// we found at least a valid answer when taken `a[pos]`. now let's try if we can also find some other answer even// if we do not take `a[pos]`.//// At first I wrote `return dfs(pos + 1, accum)`, which was a fault because even if this search returns `false` I// should return `true` since I HAVE actually found some answers. I just have not found other answers.dfs(pos+1,accum);returntrue;}intmain(){cin>>n>>k;a.resize(n);for(auto&i:a){cin>>i;}sort(begin(a),end(a),greater<>());dfs(0,0);if(kOverflow==ans_cnt){cout<<"-1\n";}else{cout<<ans_cnt<<'\n';}}
太窒息了,我 dfs 老是写假……
题目它让我们求「取一些数字,和超过 $k$」。那可以想到降序排列,先取大的,一直取到超过 $k$,设此时已经考虑了 $p$ 个数字(即,已经取了 $p$ 个数字)。此时剩下的数字数量设为 $n-p$,那么对这种情况就有 $2^{n-p}$ 种取法。
现在不取第 $p$ 个数字,从第 $p+1$ 个开始取,一直取到超过 $k$。这个过程和上一段描述的一样。此时设我们已经考虑了 $p_1$ 个数字吧!即,已经取了 $p_1 - 1$ 个数字(这是因为第 $p$ 个数字不取,我们用 $(p, p_1)$ 区间里的新数字代偿了 $p$ 号数字)。此时剩下的数字量设为 $n-p_1$,那么这种情况就有 $2^{n - p_1}$ 种取法。
重复这个过程直到所有的数都被考虑~
Orz,代码总是写假的我,第一次,把 dfs 写错成了枚举暴搜,复杂度 $O(2^n)$,光荣地超时了。第二次改了一下,结果返回值搞错了。第三次才终于写对……
代码: