题目描述

Description

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

Input

第一行两个数n，m代表物品数量及钱数
第二行n个数，代表每个物品的价格
n<=40，m<=10^18

Output

一行一个数表示购买的方案数
（想怎么买就怎么买，当然不买也算一种）

Sample Input

5 1000
100 1500 500 500 1000

Sample Output

8

题目分析

一眼搜索 然而会TLE
那么把n个物品分成两部分 每次只搜索一半
然后凑出方案数(二分)
时间复杂度

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long m,a[10000];
long long st1[2000010],st2[2000010];
int top1,top2;
void dfs(int x,long long c)
{
    if(c>m) return ;
    if(x>n/2) { st1[++top1]=c; return ; }
    dfs(x+1,c),dfs(x+1,c+a[x]);
}
void dfs2(int x,long long c)
{
    if(c>m) return ;
    if(x>n) { st2[++top2]=c; return ; }
    dfs2(x+1,c),dfs2(x+1,c+a[x]);
}
long long ans;
int check(long long x)
{
    int l=1,r=top2,pos=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(st2[mid]+st1[x]<=m) pos=mid,l=mid+1;
        else r=mid-1;
    }
    return pos;
}
int main()
{
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    dfs(1,0),dfs2(n/2+1,0);
    sort(st1+1,st1+top1+1);
    sort(st2+1,st2+top2+1);
    for(int i=1;i<=top1;i++)
        ans+=check(i);
    printf("%lld",ans);
    return 0;
}