题解:P10484 送礼物

· · 题解

题解:P10484 送礼物

题目传送门

分析一下题意可得，这道题是一道搜索。如果用最朴素的做法，一定超时。所以要考虑优化。这里使用折半搜索，分别用 suma 和 sumb 两个数组来存储折半的两次 dfs 的存储的礼物重量，排序 sumb，详见代码。在这里，由于 suma 和 sumb 存的是前一半和后一半，因此，在排完序之后，遍历 suma 用 upper_bound 来查找答案，加上 sumb_i 更新 ans 的最大值。

code：

#include<bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(),(x).end()
#define cmax(x,y) x=max(x,y)
#define cmin(x,y) x=min(x,y)
#define add(x,y) x=(x+y)%mod
#define endl '\n'
#define re register

using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
ll n,k;
int ans,cnta,cntb,N;
int suma[1<<25],sumb[1<<25];
int a[1005];
void dfs(int d,int sum[],ll s){
    if(s>k) return;
    if(d>N){
        sum[++sum[0]]=s;
        return;
    }
    dfs(d+1,sum,s);
    dfs(d+1,sum,s+a[d]);//两种选择，分别是不选当前礼物和选
}
bool cmp(int x,int y) {
    return x>y; 
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>k>>n;

    for (int i=1;i<=n;i++) cin>>a[i];   
    sort(a+1,a+n+1,cmp);//从大到小，节省时间
    N=n/2;//更新边界
    dfs(1,suma,0);
    N=n;//同上
    dfs(n/2+1,sumb,0);
    sort(sumb+1,sumb+1+sumb[0]);
    for (int i=1;i<=suma[0];i++) 
      cmax(ans,sumb[upper_bound(sumb+1,sumb+1+sumb[0],k-suma[i])-sumb-1]+suma[i]);
    cout<<ans;
    return 0;
}