CH 2401 - 送礼 - [折半DFS+二分]

题目链接：传送门

描述

作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1)以下的任意多个物品。GY希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i],G[i]<= 2^31-1。

输出格式

仅一个整数，表示GY在他的力气范围内一次性能搬动的最大重量。

样例输入

样例输出

数据范围与约定

对于20%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1

题解：

如果直接暴搜，时间复杂度 $O(2^N)$ 原地起爆，可以使用折半DFS。

礼物分成两半，前一半 $O(2^{N/2})$ 的暴搜每个礼物选不选，然后把每种方案的重量之和存到数组 $S$ 里，并且排序、去重，以备后用。

再对后一半礼物进行 $O(2^{N/2})$ 暴搜，每种方案得到了重量后，去前面 $S$ 里二分找两个重量和加起来最大，且不超过 $W$ 的那个 $S[i]$。

优化后的时间复杂度是 $O(2^{N/2} \cdot \log 2^{N/2}) = O(N \cdot \sqrt{2}^N)$。

原本想用状压，发现应该是被卡了，因为状态转成重量还要凭空再多 $O(N)$ 的复杂度，比较尴尬……以后码代码前得记得先算算复杂度……别拿个假算法死怼半天……

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

int n,x;

ll w,g[maxn];

int tot;

ll S[<<(maxn>>)];

void dfs(int p,ll sum)

{

    if(sum>w) return;

    if(p>x)

    {

        S[++tot]=sum;

        return;

    }

    dfs(p+,sum);

    dfs(p+,sum+g[p]);

}

ll ans;

ll srch(ll x)

{

    int l=, r=tot;

    while(l<r)

    {

        int mid=(l+r+)>>;

        if(S[mid]<=x) l=mid;

        else r=mid-;

    }

    return S[l];

}

void dfs2(int p,ll sum)

{

    if(sum>w) return;

    if(p>n)

    {

        ans=max(ans,sum+srch(w-sum));

        return;

    }

    dfs2(p+,sum);

    dfs2(p+,sum+g[p]);

}

int main()

{

    cin>>w>>n, x=(n+)/;

    for(int i=;i<=n;i++) scanf("%d",&g[i]);

    sort(g+,g+n+,greater<int>());

    tot=;

    dfs(,0LL);

    sort(S+,S+tot+);

    tot=unique(S+,S+tot+)-(S+);

    ans=;

    dfs2(x+,0LL);

    cout<<ans<<endl;

}

Gy