原题链接
题意：
给n个物品和对应的价格，问用不超m元的钱可以买到的物品的方案数。
思路：
折半搜索的入门题（雾.jpg）
n的范围是n<=40。普通的搜索一定会TLE，考虑将物品分成两部分来搜索，这样时间复杂度就变成了2^(𝑛/2+1)；
基本思路就是对[1,mid] 和[mid+1],n两个区间都进行dfs，分别记录答案，再将两个答案区间合并。
就本题而言，a数组表示对[1,mid]进行搜索，得到的方案；b数组表示对[mid+1,n]进行搜索，得到的方案。
区间合并时，对于a,b数组里的任意两个数，只要和<=m都是合法的方案数，朴素解法是两层for枚举，只能过40%的数据。优化是先将a数组从小到大排序，再遍历b数组，在a数组里二分查找b[i]+a[pos]<=m的最大的pos值，这样pos之前的数一定也满足该式。
代码：
注意数组大小。
const int maxn=1e7+100; ll n,m; ll w[maxn],a[maxn],b[maxn]; ll cnta=0,cntb=0; void dfs(ll l,ll r,ll sum,ll a[],ll &cnt){ if(sum>m) return ;///剪枝 if(l>r){ a[++cnt]=sum;return ;///搜索完成 } dfs(l+1,r,sum+w[l],a,cnt);///选当前数 dfs(l+1,r,sum,a,cnt);///不选当前数 } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) w[i]=read(); ll mid=n/2;///折半搜索 dfs(1,mid,0,a,cnta); dfs(mid+1,n,0,b,cntb); sort(a+1,a+1+cnta);///对a数组进行排序 ll res=0; for(int i=1;i<=cntb;i++){ ///遍历b数组 看b[i]和前面的几个数的和不超过m res+=upper_bound(a+1,a+1+cnta,m-b[i])-(a+1); } out(res); return 0; }
