买瓜题解

1.题意简述

有 n 个瓜，对于每个瓜，有买整个，买半个，不买三种选择，求最少要买多少个半个瓜。

2.简要分析

这道题目，dp 显然会超空间，所以自然地想到搜索。

然后输入的时候乘 2，m 也乘 2，答案不变，不用处理小数了。

3.折半搜索

朴素的爆搜时间复杂度是 O(3^{20}) 的，那么我们就可以使用折半搜索了。

普通的折半搜索代码如下。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000010];
int ans=1e9+10;
int N;
unordered_map<int,int> v;
void dfs1(int k,int q,int sum)
{
    if(sum>m||k>n+1)
        return;
    if(sum==m){
        v[sum]=q;
        return;
    }
    if(k==N+1)
    {
        if(v[sum])v[sum]=min(v[sum],q+1);
        else v[sum]=q+1;
        return;
    }
    dfs1(k+1,q,sum);
    dfs1(k+1,q+1,sum+a[k]/2);
    dfs1(k+1,q,sum+a[k]);
}
void dfs2(int k,int q,int sum)
{
    if(sum>m||k>n+1)
        return;
    if(sum==m){
        ans=min(ans,v[sum]+q);
        return;
    }
    if(k==n+1)
    {
        if(v[m-sum])ans=min(ans,q+v[m-sum]-1);
        return;
    }
    dfs2(k+1,q,sum);
    dfs2(k+1,q+1,sum+a[k]/2);
    dfs2(k+1,q,sum+a[k]);
}
int main()
{
    cin>>n>>m;
    m*=2;
    N=min(n-2,n/2);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]*=2;
    }
    sort(a+1,a+1+n);
    dfs1(1,0,0);
    dfs2(N+1,0,0);
    cout<<ans;
    return 0;
}

这样，你就可以得到 32pts 的好成绩（逃）。

但是，这样不是我们想要的。

4.剪枝+优化

剪枝 1：如果当前答案比要输出的答案大了，直接返回就行。

剪枝 2：维护瓜重量后缀和，假如当前重量加上后缀和比 m 要小，直接返回。

优化 3：将原数组进行排序，具体原因戳我。

优化 4：unordered_map 常数大，所以用平板电视。

优化 5：要把贡献大的放到前面搜索。

5.完整代码

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int n,m;
int a[1000010];
int ans=1e9+10;
int N;
cc_hash_table <int,int> v;
int b[100010];
int cnt;
void dfs1(int k,int q,int sum)
{
    if(sum>m)
        return;
    if(sum+b[k]<m) return;
    if(sum==m){
        v[sum]=q;
        return;
    }
    if(k==N+1)
    {
        if(v[sum])v[sum]=min(v[sum],q+1);
        else v[sum]=q+1;
        return;
    }dfs1(k+1,q,sum+a[k]);dfs1(k+1,q+1,sum+a[k]/2);
    dfs1(k+1,q,sum);

}
void dfs2(int k,int q,int sum)
{
    if(sum>m||q>ans)
        return;
    if(sum==m){
        ans=min(ans,v[sum]+q);
        return;
    }
    if(k==n+1)
    {
        if(v[m-sum])ans=min(ans,q+v[m-sum]-1);
        return;
    }dfs2(k+1,q,sum+a[k]);dfs2(k+1,q+1,sum+a[k]/2);
    dfs2(k+1,q,sum);

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    m*=2;
    N=n/2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]*=2;
    }
    sort(a+1,a+1+n);
    for(int i=n;i>=1;i--) b[i]=b[i+1]+a[i];
    dfs1(1,0,0);
    dfs2(N+1,0,0);
    if(ans==1e9+10)
    {
        cout<<"-1";
        return 0;
    }
    cout<<ans;
    return 0;
}