BZOJ_4800_[Ceoi2015]Ice Hockey World Championship_双指针

BZOJ_4800_[Ceoi2015]Ice Hockey World Championship_双指针

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

---

把序列分成两半，分别搜出所有状态。然后排个序双指针解决。

 

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

typedef unsigned long long ll;

int n,mid;

ll w[50],a[2000050],b[2000050],m;

int la,lb;

void dfs1(int dep,ll sum) {

	if(dep==mid) {

		a[++la]=sum; return ;

	}

	if(w[dep+1]+sum<=m) dfs1(dep+1,sum+w[dep+1]);

	dfs1(dep+1,sum);

}

void dfs2(int dep,ll sum) {

	if(dep==n) {

		b[++lb]=sum; return ;

	}

	if(w[dep+1]+sum<=m) dfs2(dep+1,sum+w[dep+1]);

	dfs2(dep+1,sum);

}

int main() {

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

	//freopen("shopping.out","w",stdout);

	scanf("%d%llu",&n,&m);

	int i;

	for(i=1;i<=n;i++) {

		scanf("%llu",&w[i]);

	}

	if(n==1) {

		printf("%d\n",1+(w[1]<=m)); return 0;

	}

	mid=(n+1)>>1;

	dfs1(0,0);

	dfs2(mid,0);

	int j=lb;

	sort(a+1,a+la+1); sort(b+1,b+lb+1);

	ll ans=0;

	for(i=1;i<=la;i++) {

		while(j&&b[j]+a[i]>m) j--;

		if(j==0) break;

		ans+=j;

	}

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

}