[洛谷 4799][CEOI2015 Day2]世界冰球锦标赛

题目链接

https://www.luogu.org/problem/P4799

题解

考虑折半搜索来解决问题。

我们将价值数组分成两半，搜索的时候只从其中一半里选择，并记录每次搜索回溯时的花费。

计数的时候，我们针对每个状态，算出能和这个状态搭配的另一半搜索的状态数。

通过将状态数组排序后二分查找，每个状态可以在 \(O(\log n)\) 的时间内算出能与它搭配的状态数。

#include <iostream>
#include <algorithm>
using namespace std;
long long a[45],n,m,resa[1500005],resb[1500005],ans;
void dfs(int l,int r,long long used,long long p[],long long&cnt)
{
 if(used>m)return;
 if(l>r)
 {
  p[++cnt]=used;
  return;
 }
 dfs(l+1,r,used+a[l],p,cnt);
 dfs(l+1,r,used,p,cnt);
}
int main()
{
 cin>>n>>m;
 long long mid=n>>1,cnta=0,cntb=0;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 dfs(1,mid,0,resa,cnta);
 dfs(mid+1,n,0,resb,cntb);
 sort(resa+1,resa+cnta+1);
 for(int i=1;i<=cntb;i++)
  ans+=upper_bound(resa+1,resa+cnta+1,m-resb[i])-resa-1;
 cout<<ans<<endl;
 return 0;
}