题解：P10484 送礼物

RpUtl · 2024-05-17 15:50:25 · 题解

一道很经典的搜索题目。

题意简述

给定 n 个正整数 G_i。请选择一种方案，选择其中若干个 G_i 使得他们的和不超过给定的 W。

思路分析

对于这道题，我们可以使用搜索算法。

如果是普通的搜索，我们枚举每一个数选或不选，然后取最大的合法方案，这样的时间复杂度为 O(2^n)，此题中 n\le 46，显然无法通过。

我们可以进行简单的优化，依照上面的原始算法，我们跑两趟 DFS，第一次 DFS 求出 1\sim \lfloor\frac{n}{2}\rfloor 内所有方案，第 i 种方案的和记为 A_i，第二次 DFS 求出 \lfloor\frac{n}{2}\rfloor+1\sim n 内所有方案，第 j 种方案的和记为 B_j。

对于每个 A_i，我们找到最大的 B_j 使得 A_i+b_j\le W，并用 A_i+B_j 更新答案。显然，最大的 B_j 必然不超过 W-A_i，用二分查找求值即可。

两次 DFS 的时间复杂度为 O(2^{\lfloor\frac{n}{2}\rfloor})。更新答案的时间复杂度为 O\left(2^{\lfloor\frac{n}{2}\rfloor}n\right)，可以通过本题。

这种做法的实质是将一次搜索划分为了两次搜索，因为搜索的搜索量随搜索树的数高而指数级增加，这样进行折半搜索，降低了搜索树的树高。这种经典的搜索方法成为“双向搜索”。建议完成本题后去了解字串变换这道题。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=(1<<25);
typedef long long ll;
ll a[N],g[47],n,w,cnt,ans,m,p;
ll r(){
    ll x=0;char ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
bool cmp(int a,int b){
    return a<b;
}
bool cmp2(int a,int b){
    return a>b;
}
ll found(int x){
    ll l=1,r=m,mid,ans=0;
    while(l<r){
        mid=(l+r+1)/2;
        if(a[mid]>x)r=mid-1;
        else if(a[mid]<x)l=mid,ans=a[mid];
        else if(a[mid]==x)return x;
    }
    return ans;
}
void dfs1(ll idx,ll sum){
    if(idx>p){
        a[++cnt]=sum;
        return;
    }
    dfs1(idx+1,sum);
    if(sum+g[idx]<=w)dfs1(idx+1,sum+g[idx]);
    return;
}
void dfs2(ll idx,ll sum){
    if(idx>n){
        ans=max(ans,sum+found(w-sum));
        return;
    }
    dfs2(idx+1,sum);
    if(sum+g[idx]<=w)dfs2(idx+1,sum+g[idx]);
}
int main(){
    w=r(),n=r();
    for(int i=1;i<=n;i++)g[i]=r();
    sort(g+1,g+1+n,cmp2);
    p=n/2+2;
    dfs1(1,0);
    sort(a+1,a+1+cnt,cmp);
    m=unique(a+1,a+1+cnt)-(a+1);
    dfs2(p+1,0);
    printf("%lld",ans);
    return 0;
}

如有错误，请指出。