[蓝桥杯 2023 省 A] 买瓜 --暴力DFS+剪枝优化

题目来自洛谷：

暴力思路：

①根据题目，可以知道有三种操作，第一种操作选择这个瓜，第二种操作不选择这个瓜，第三种操作选择这个瓜的一半。我们可以用一个res来记录这三种操作返回的结果，最后在返回这三种操作的最小值。

②从数据样例中知道，对于第三种操作，在进行切一半操作的时候，数据类型会发生改变，int只能存整数，这样会导致答案错误。因此我们存数据前对数据进行*2操作，同时我们的总重量也要 m*2。

③由于本题数据过大，会爆int，我们要用long long 来存。

#include<bits/stdc++.h>
//long long 来存数据
#define int long long
using namespace std;
const int N = 40;

int n, m;
int arr[N];//存数据
int w[N]; //后缀和

//x表示枚举瓜 sum 表示当前重量
int dfs(int x, int sum){
    if(sum == 2*m){
        return 0;
    }
    //遍历完了所有瓜
    if(x > n){
        return N;
    }
    //当前重量超过总重量 不合法
    if(sum > 2*m){
        return N;
    }
    //当前重量+加上当前点后缀和小于总重量 不合法
    if(sum + w[x] < 2*m){
        return N;
    }
    //直接选
    int res1 = dfs(x+1, sum + arr[x]);
    //选一半
    int res3 = dfs(x+1, sum + arr[x] / 2) +1;
    //不选
    int res2 = dfs(x+1, sum);
    return min({res1, res2, res3});
}

signed main(){
    cin >> n >> m;
    //在存入数据之前 将数据*2 
    //后续操作不需要使用 double
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        arr[i] = 2*x;
    }
    //将arr数组从大到小排序
    sort(arr+1, arr+n+1);reverse(arr+1, arr+n+1);
    //后缀和
    for(int i = n; i >= 1; i--){
        w[i] = w[i+1] + arr[i];
    }
    //得到答案
    int res =  dfs(1, 0);
    //判断一下 能不能买到总重量恰好为m的瓜
    if(res == N){
        cout << "-1" << endl;
    }else{
        cout << res << endl;
    }
    return 0;
}