洛谷P4799 世界冰球锦标赛

题目描述
译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式
第一行，两个正整数 NN 和 M(1 \leq N \leq 40,1 \leq M \leq 10^{18})M(1≤N≤40,1≤M≤10
18
)，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，NN 个以空格分隔的正整数，均不超过 10^{16}10
16
，代表每场比赛门票的价格。

输出格式
输出一行，表示方案的个数。由于 NN 十分大，注意：答案 \le 2^{40}≤2
40
。

输入输出样例
输入 #1复制
5 1000
100 1500 500 500 1000
输出 #1复制
8
说明/提示
样例解释
八种方案分别是：

一场都不看，溜了溜了
价格 100100 的比赛
第一场价格 500500 的比赛
第二场价格 500500 的比赛
价格 100100 的比赛和第一场价格 500500 的比赛
价格 100100 的比赛和第二场价格 500500 的比赛
两场价格 500500 的比赛
价格 10001000 的比赛
有十组数据，每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示：

数据组号 1-21−2 3-43−4 5-75−7 8-108−10
N \leqN≤ 1010 2020 4040 4040
M \leqM≤ 10^610
6
10^{18}10
18
10^610
6
10^{18}10
18
上代码：

#include
#define int long long
using namespace std;
int n,m,dis[100],ans;
vector<int> a,b;
void dfs(int k,int sum,int tp)
{
	if (tp==1)
	{
		if (k>n)
		{
			b.push_back(sum);
			return;
		}
    } else 
    {
    	if (k>n/2)
    	{
    		a.push_back(sum);
    		return;
    	}
    }
	dfs(k+1,sum+dis[k],tp);
	dfs(k+1,sum,tp);
}
signed main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>dis[i];
	dfs(1,0,0);
	dfs(n/2+1,0,1);
	sort(a.begin(),a.end());
	for (int i=0;i<b.size();i++)
	{
		int l,r,mid,cnt=-1;
		l=0;r=a.size()-1;
		while (l<=r)
		{
			mid=l+(r-l)/2;
			if (a[mid]<=m-b[i])
			{
				cnt=mid;
				l=mid+1;
			} else r=mid-1;
		}
		ans+=cnt+1;
	}
	cout<<ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49