[2014-10-29 模拟赛] 买汽水

2014-10-30
竞赛题解 / 搜索
DFSNOIP模拟赛

描述 Description

暑期集训一共 N 天，大家都辛苦了，Symbol 准备给大家买汽水，但是钱只有 M。

每天买汽水的花销都是不固定的，如果不够钱，买到的汽水不够大家一起喝，那样子不太好对不对？所以我们要买的话，就得让每个人都能喝到汽水要不我们那天就不买了。现在给出每天买汽水的花销，请问我们一共最多能够花掉 Symbol 多少钱呢？

暑假最多不超过 40 天，Symbol 给大家花的钱最多有一亿。

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

3 77567506
10856 8595 24637

样例输出 SampleOutput

44088

NOIP 模拟赛

代码 Code

分成两半搜索，二分查找最大值更新答案。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
#define ll long long
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k;
int a[45];
vector <int> v;
ll z,y,x,ans=0;
void dfs(int s)
{
    int i,j,t;
    if (s==n>>1)
    {
        if ((ll)x+a[s]<=m) v.push_back(x+a[s]);
        v.push_back(x);
        return ;
    }
    if (s==n)
    {
        x+=a[s];
        if (x<=m) 
        {
            t=lower_bound(v.begin(),v.end(),m-x)-v.begin();
            if (t==v.size() || v[t]+x>m) t--;
            if (t>=0) ans=max(ans,v[t]+x);
        }
        x-=a[s];
        if (x<=m)
        {
            t=lower_bound(v.begin(),v.end(),m-x)-v.begin();
            if (t==v.size() || v[t]+x>m) t--;
            if (t>=0) ans=max(ans,v[t]+x);
        }
        return ;
    }
    x+=a[s];
    if (x<=m) dfs(s+1);
    x-=a[s];
    if (x<=m) dfs(s+1);
}
int main()
{
    freopen("drink.in","r",stdin);
    freopen("drink.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    v.clear();
    x=0;
    dfs(1);
    sort(v.begin(),v.end());
    x=0;
    dfs((n>>1)+1);
    printf("%d\n",ans);
    return 0;
}