买瓜

Melting_Pot · 2023-09-19 19:18:35 · 题解

题目链接

首先爆搜不用说，别读错题就行（可以不买瓜，希望没人和我一样读错）。答案的合并是比较套路的 meet in the middle，直接开桶维护即可。但是这样还是不足以通过本题，因此我们考虑剪枝：

1. 最优性剪枝：如果当前答案已经大于最优解，剪掉。
2. 可行性剪枝：如果当前答案已经超标，剪掉。
3. 优化搜索顺序：这没啥好说的，sort 一下就行。

code

#include<bits/stdc++.h>
#define int long long
#define inf 1e9+10
using namespace std;
const int N=50;
int n,m,ans(inf),mid;
int a[N];
unordered_map<int,int> mp;
void dfs1(int dep,int sum,int num){
    if(sum>m||num>ans) return;
    if(sum==m) return ans=min(ans,num),void();
    if(dep==mid+1){
        if(mp.count(sum)) mp[sum]=min(mp[sum],num);
        else mp[sum]=num;
        return;
    }
    dfs1(dep+1,sum,num);
    dfs1(dep+1,sum+a[dep],num);
    dfs1(dep+1,sum+a[dep]/2,num+1);
}
void dfs(int dep,int sum,int num){
    if(sum>m||num>ans) return;
    if(sum==m) return ans=min(ans,num),void();
    if(dep==n+1){
        if(mp.count(m-sum)) ans=min(ans,mp[m-sum]+num);
        return;
    }
    dfs(dep+1,sum,num);
    dfs(dep+1,sum+a[dep],num);
    dfs(dep+1,sum+a[dep]/2,num+1);
}
signed main(){
    // freopen("1.in","r",stdin);
    scanf("%lld%lld",&n,&m);
    m<<=1;
    mid=max(1ll,n/2);
    for(int i=1;i<=n;++i) scanf("%lld",a+i);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) a[i]<<=1;
    dfs1(1,0,0);
    dfs(mid+1,0,0);
    if(ans>=inf) return puts("-1")&0;
    cout<<ans;
    return 0;
}