学步园

问题描述

暑期集训一共N天，大家都辛苦了，Symbol准备给大家买汽水，但是钱只有M。
每天买汽水的花销都是不固定的，如果不够钱，买到的汽水不够大家一起喝，那样子不太好对不对？所以我们要买的话，就得让每个人都能喝到汽水要不我们那天就不买了。现在给出每天买汽水的花销，请问我们一共最多能够花掉Symbol多少钱呢？
暑假最多不超过40天，Symbol给大家花的钱最多有一亿。

输入

输入第一行有两个整数N，M。 1<=N<=40，0<=M<=100000000。
接下来一行有N个数，表示某一天的汽水花销。每天汽水的花销p<=100000000。

输出

输出一个整数，表示我们能够花掉Symbol多少钱。

输入输出样例一

drink.in drink.out
3 10
1 2 3 6

输入输出样例二

drink.in drink.out
4 10
4 3 5 11 9

数据描述

对于10%的数据，N<=10。
对于30%的数据，N<=20。
对于60%的数据，N<=30。
对于100%的数据，N<=40。

题解

感觉自己越来越弱了，搜索60分。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,tot,a[45];
int ans,sum[45];
bool kp(const int i,const int j) {return i>j;}
void init()
{
	scanf("%d%d",&n,&m);
	int i,x;
	for(i=1;i<=n;i++)
	   {scanf("%d",&x);
	    if(x<=m) a[++tot]=x;
	   }
	n=tot;
	sort(a+1,a+n+1,kp);
	for(i=n;i>0;i--) sum[i]=sum[i+1]+a[i];
	//for(i=1;i<=n;i++) printf("%d ",sum[i]);
	//printf("\n");
}
void dfs(int w,int ct)
{
	if(w>n) {ans=max(ct,ans); return;}
	if(ct+sum[w]<=m&&ct+sum[w]>ans) {ans=ct+sum[w]; return ;}
	if(ct+sum[w]<ans) return;
	if(ct+a[w]<=m) dfs(w+1,ct+a[w]);
	dfs(w+1,ct);
}
int main()
{
	freopen("drink.in","r",stdin);
	freopen("drink.out","w",stdout);
	init(); dfs(1,0);
	printf("%d\n",ans);
	return 0;
}

正解可以分两块搞，我比较懒就没有写精妙的hash。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,tot,a[45],fen;
int ans,hs[5000000],top;
bool kp(const int i,const int j) {return i>j;}
void init()
{
	scanf("%d%d",&n,&m);
	int i,x;
	for(i=1;i<=n;i++)
	   {scanf("%d",&x);
	    if(x<=m) a[++tot]=x;
	   }
	n=tot;
	sort(a+1,a+n+1,kp);
}
void dfs1(int w,int ct)
{
	if(w>n)
	   {hs[++top]=ct; return;}
	if(ct+a[w]<=m) dfs1(w+1,ct+a[w]);
	dfs1(w+1,ct);
}
void erf(int x)
{
	int l=1,r=top,mid,y;
	while(l<=r)
	   {mid=(l+r)>>1;
	    if(hs[mid]+x<=m) {y=hs[mid]; l=mid+1;}
	    else r=mid-1;
	   }
	ans=max(ans,y+x);
}
void dfs2(int w,int ct)
{
	if(w>fen)
	   {erf(ct); return;}
	if(ct+a[w]<=m) dfs2(w+1,ct+a[w]);
	dfs2(w+1,ct);
}
int main()
{
	freopen("drink.in","r",stdin);
	freopen("drink.out","w",stdout);
	init();
	fen=n>>1; dfs1(fen+1,0);
	sort(hs+1,hs+top+1);
	dfs2(1,0);
	printf("%d\n",ans);
	return 0;
}