[BZOJ 4800][Ceoi2015]Ice Hockey World Championship：双向搜索

本文主要是介绍[BZOJ 4800][Ceoi2015]Ice Hockey World Championship：双向搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

双向搜索模板题，n/2<=20刚好可以逐项枚举

/*
User:Small
Language:C++
Problem No.:4800
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
int n,tota,totb,hal;
ll m,a[(1<<20)+5],b[(1<<20)+5],ans,w[45];
int main(){freopen("data.in","r",stdin);//scanf("%d%lld",&n,&m);hal=n/2; for(int i=1;i<=n;i++)scanf("%lld",&w[i]);for(int i=0;i<(1<<hal);i++){ll tmp=0;for(int j=0;j<hal;j++)if((i>>j)&1) tmp+=w[j+1];a[++tota]=tmp;}for(int i=0;i<(1<<(n-hal));i++){ll tmp=0;for(int j=0;j<(n-hal);j++)if((i>>j)&1) tmp+=w[hal+j+1];b[++totb]=tmp;}sort(a+1,a+tota+1);sort(b+1,b+totb+1);for(int i=1,j=totb;i<=tota&&a[i]<=m;i++){while(a[i]>m-b[j]&&j) j--;ans+=j;}printf("%lld\n",ans);return 0;
}

这篇关于[BZOJ 4800][Ceoi2015]Ice Hockey World Championship：双向搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---