【JZOJ5264】化学

Description

Input

Output

Sample Input

3 10
1 2 10

Sample Output

Hint

题解:

　　这个题目通过30%部分分的提示,我们可以猜出这个题目的正解就是折半搜索(然而我还是没做出来,毕竟是第一次写这种题吧!),我们考虑,先搜出前一半的,将所有方案的话费都记下来(存在f数组中),sort一遍,然后搜下一半,搜到最后的时候,对于每种方案(记后一半的花费为w),显然只要w+f[i]<=m就是合法方案,所以对于每个方案我们可以二分出最大的合法前一半方案的位置,直接统计答案就可以了.

代码:

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#define ll long long

using namespace std;

ll coss[],f[<<];

ll n,m,tot,nn,anss=;

void dfs1(int now,int co){

    if(co>m) return;

    if(now==nn+){

        f[++tot]=co;

        return;

    }

    dfs1(now+,co+coss[now]);

    dfs1(now+,co);

}

void dfs2(int now,int co){

    if(co>m) return;

    if(now==n+){

        int l=,r=tot,mid,ans=;

        while(l<=r){

            mid=(l+r)/;

            if(f[mid]+co<=m) ans=mid,l=mid+;

            else r=mid-;

        }

        anss+=ans;

        return;

    }

    dfs2(now+,co+coss[now]);

    dfs2(now+,co);

}

int main()

{

    scanf("%lld%lld",&n,&m);nn=n/;

    for(int i=;i<=n;i++) scanf("%lld",&coss[i]);

    dfs1(,);

    sort(f+,f+tot+);

    dfs2(nn+,);

    printf("%lld",anss);

    return ;

}

巴特西