【BZOJ4800】 [Ceoi2015]Ice Hockey World Championship-白红宇

【BZOJ4800】 [Ceoi2015]Ice Hockey World Championship

阅读量：6287 次

发布时间：2019-06-22

本文共 2215 字，大约阅读时间需要 7 分钟。

4800: [Ceoi2015]Ice Hockey World Championship

Time Limit: 10 Sec Memory Limit: 256 MB

Submit: 68 Solved: 30

[][][]

Description

有n个物品，m块钱，给定每个物品的价格，求买物品的方案数。

Input

第一行两个数n，m代表物品数量及钱数

第二行n个数，代表每个物品的价格

n<=40，m<=10^18

Output

一行一个数表示购买的方案数

（想怎么买就怎么买，当然不买也算一种）

Sample Input

5 1000

100 1500 500 500 1000

Sample Output

HINT

Source

sol：

meet in the middle

太感人了我刚打完板子今天就看见一道题

具体来说我们分开暴力枚举前20个物品放不放后20个物品放不放将答案记录到数组a和数组b中（爆搜）

复杂度$O（2^{20}*2)$

当然现在答案肯定不对我们枚举a中每一个元素假设其为x 在b中二分m-x 看看贡献是多少

贡献就是b的下标。然后ans+=b的下标即可。

复杂度$O(2^{20}log2^{20}+2^{20}*2+2^{20}log2^{20})$

//Meet In The Middle/*In Search Of Life*/#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #define debug(x) cerr<<#x<<"="<
                 
                  <
                  
                    pii;typedef long long ll;inline int init(){ int now=0,ju=1;char c;bool flag=false; while(1) { c=getchar(); if(c=='-')ju=-1; else if(c>='0'&&c<='9') { now=now*10+c-'0'; flag=true; } else if(flag)return now*ju; }}inline long long llinit(){ long long now=0,ju=1;char c;bool flag=false; while(1) { c=getchar(); if(c=='-')ju=-1; else if(c>='0'&&c<='9') { now=now*10+c-'0'; flag=true; } else if(flag)return now*ju; }}ll a[1005];ll res[3000005];int n;ll m;#ifdef unix #define LLD "%lld"#else #define LLD "%I64d"#endifll nex[3000005];int pren=n/2;ll pans=0;ll ans=0;int pcnt=0,ncnt=0;int bSearch(int l,int r,ll x){ int pos=-1; int mid=((l+r)>>1); while(l<=r) { mid=((l+r)>>1); if(res[mid]>x) { r=mid-1; } else { l=mid+1; pos=mid; } } return pos;}void predfs(int now,ll V){ if(V>m)return; if(now==pren+1) { res[++pcnt]=V; return; } predfs(now+1,V+a[now]); predfs(now+1,V); return;}void nextdfs(int now,ll V){ if(V>m)return; if(now==n+1) { nex[++ncnt]=V; return; } nextdfs(now+1,V+a[now]); nextdfs(now+1,V); return;}void MeetInTheMiddle(){ for(int i=1;i<=ncnt;i++) { ans+=bSearch(1,pcnt,m-nex[i]); } return;}int main(){ n=init();m=llinit(); for(int i=1;i<=n;i++) { a[i]=llinit(); } pren=n/2; predfs(1,0); nextdfs((n/2)+1,0); sort(res+1,res+pcnt+1); MeetInTheMiddle(); printf(LLD,ans); return 0;}