4800: [Ceoi2015]Ice Hockey World Championship(折半搜索)

4800: [Ceoi2015]Ice Hockey World Championship

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 622 Solved: 311
[Submit][Status][Discuss]

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

#include<bits/stdc++.h>

#define N 45

#define M 1000007

#define ll long long

using namespace std;

ll n,m,ans,cnt,mx,flag;

ll val[N],f[N][M];

inline ll read()

 {

     ll x=,f=;char c=getchar();

     while(c>''||c<''){if(x=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

void dfs(int k,ll sum)

{

    if(sum>m) return;

    if(k==n)

    {

        ans++;return;

    }

    dfs(k+,sum);

    dfs(k+,sum+val[k+]);

}

void dp()

{

    f[][m]=;

    for(int i=;i<=n;i++) for(int j=;j<=m;j++)

    {

        f[i][j]+=f[i-][j]+f[i-][j+val[i]];

    }

    for(int i=;i<=m;i++) ans+=f[n][i];

}

int main()

{

    //freopen("ly.in","r",stdin);

    n=read();m=read();

    for(int i=;i<=n;i++) val[i]=read();

    if(m<=1e6) dp();

    else dfs(,);

    printf("%lld\n",ans);

    return ;

}

80暴力 dfs+dp

/*

折半搜索

*/

#include<bits/stdc++.h>

#define ll long long

#define N 55

using namespace std;

ll n,m,mid,cnta,cntb,ans;

ll w[N],suma[<<],sumb[<<];

inline ll read()

 {

     ll x=,f=;char c=getchar();

     while(c>''||c<''){if(x=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

inline void dfs(int l,int r,ll sum,ll a[],ll &cnt)

{

    if(sum>m)return;

    if(l>r)

    {

        a[++cnt]=sum;return;

    }

    dfs(l+,r,sum+w[l],a,cnt);

    dfs(l+,r,sum,a,cnt);

}

int main()

{

    n=read();m=read();

    for(int i=;i<=n;i++)w[i]=read();;

    mid=n/;

    dfs(,mid,,suma,cnta);

    dfs(mid+,n,,sumb,cntb);

    sort(suma+,suma++cnta);

    for(int i=; i<=cntb; i++)

        ans+=upper_bound(suma+,suma++cnta,m-sumb[i])-suma-;

    printf("%lld\n",ans);

    return ;

}

巴特西