题解 P4799 【[CEOI2015 Day2]世界冰球锦标赛】
顾z
2018-11-24 19:51:58
退役选手日常划水。
显然这个题直接dfs是过不去的$O(2^n)$
但是我们可以一半一半的搜,即**折半搜索**,复杂度可以降到$O(2^{\frac{n}{2}})$
所以我们取一个$mid$,分别搜前半段和后半段。
然后合并答案的时候就需要令某一个数组变得有序,在其中找到最靠右的合法位置,直接累加即可。
这里用到了$upper$_$bound$
``代码``
```c++
#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register
#define lo long long
using namespace std;
const int gz=1e6+6e5;
inline void in(R lo &x)
{
R int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
lo a[gz],b[gz],mon[42],ans,m;
int sum,cnt,n,mid;
void dfs(R int dep,R lo now)
{
if(now>m)return;
if(dep>mid)
{
a[++cnt]=now;
return;
}
dfs(dep+1,now+mon[dep]);
dfs(dep+1,now);
}
void dfss(R int dep,R lo now)
{
if(now>m)return;
if(dep>n)
{
b[++sum]=now;
return;
}
dfss(dep+1,now+mon[dep]);
dfss(dep+1,now);
}
int main()
{
scanf("%d%lld",&n,&m);
for(R int i=1;i<=n;i++)in(mon[i]);
mid=(n+1)/2;
dfs(1,0);dfss(mid+1,0);
sort(b+1,b+sum+1);
for(R int i=1;i<=cnt;i++)
ans+=upper_bound(b+1,b+sum+1,m-a[i])-b-1;
printf("%lld",ans);
}
```