本文主要是介绍蓝桥杯2023年第十四届省赛真题-买瓜|DFS+剪枝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
0买瓜 - 蓝桥云课 (lanqiao.cn)
蓝桥杯2023年第十四届省赛真题-买瓜 - C语言网 (dotcpp.com)
（蓝桥官网的数据要求会高一些）
说明：
这道题可以分析出：对一个瓜有三种选择：
- 不拿，切的次数不变，买瓜的重量不变
- 拿一半，切的次数加一，加这个瓜一半的重量
- 拿一整个瓜，切的次数不变，加这个瓜的重量
所以，DFS程序分支数确定为三个，传递的参数确定为：现在买到的重量cw，现在切的个数cnt，选到几个瓜了k。
终止条件1为：n个瓜全部都选择完毕；
终止条件2为：买的瓜重量到达m。
但是由于n的范围在1到30，所以时间复杂度达到了O()，会超时。必须考虑剪枝。
那么比较任意想到的剪枝思路有三种：
1.当前的重量加上剩下所有的瓜都小于m，肯定不能找到答案了，不继续向下找了。于是就先预处理，预先计算出第i个瓜到最后一个瓜的总重量 ，在dfs的时候好使用。
2.当前的重量（小于m的情况下）加上最小的瓜的一半重量都大于m，肯定不行。
3.当前切的次数比找到的次数多或者相同了，剪掉。
那么剪枝的几个方法就确定了，我比较喜欢在递归分支前加判断，能递归下去才递归，避免栈的频繁调用。所以三个分支前都加了if语句。
这里还需要注意：
1.long long的范围是大于e18的，所以质量可以都乘2处理，防止出现小数。但是本题用小数也能全通过样例。如果用小数，在处理小数的比较相等的时候，要采用差值绝对值小于一个很小的数的方式，瓜的重量也要除以2.0 。
2.要对瓜预先排序，但排序必须降序排（降序排之后就能AC了），先选大的，更快排除一些搜索的分支。题目要求的其实就是尽量买整个的瓜。所以在写dfs分支时也把买整个的分支放在第一位。注意c++默认是升序排列，降序要这样写：
//降序 sort(A.begin()+1,A.end(),greater<int>());
在洛谷的题解区有优化成折半搜索的解法，但放在蓝桥官网上AC不了，所以不再说明，只放个链接：P9234 [蓝桥杯 2023 省 A] 买瓜 - 洛谷 | 计算机科学教育新生态 (lu
ogu.com.cn)
代码如下：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N =30+10;
int ans = 0;
int n;
int m,sum[N];
vector<int> A;void dfs(int k,int cnt,double cw){if(cnt>=ans) return;//是 绝对值 小于 一个极小的数 if(abs(cw-m)<1E-5){ans=cnt;return;}if(sum[k]+cw<m) return;//要在判断重量是否合法之后再判断k，因为我的选择 第n个瓜的重量之后，在k=n+1的时候才体现 if(k>n) return;//if(cw>m) return;if(cw+A[k]<=m) dfs(k+1,cnt,cw+A[k]);if(cw+A[k]/2.0<=m&&(cnt+1)<ans) dfs(k+1,cnt+1,cw+A[k]/2.0);//前面判断了cw 是否等于m，这里肯定cw小于m，如果加上最小的重量都大于m，那么这个分支就不能找到合法答案 if(cw+A[n]/2.0>m) return;dfs(k+1,cnt,cw);}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;//瓜的个数，想要的总重量 ans=n+1;A.assign(n+1,0);for(int i=1;i<=n;i++){cin>>A[i];
//如果有一个瓜重量等于m直接可以得出答案，当然这里也可以判断一次每个瓜切成两半
//有没有等于m的if(A[i]==m) {ans=0;}}//关键：降序sort(A.begin()+1,A.end(),greater<int>());sum[n]=A[n];//预处理 算出从第i个瓜到最后一个瓜的总重量 for(int i=n-1;i>=1;i--){sum[i]=sum[i+1]+A[i];} if(A[n]>m){cout<<-1;}else{if(ans==n+1)dfs(1,0,0);//不用单独再用一个变量来标志了，直接用ans的变化来标识是否至少找到一个合法的答案if(ans!=n+1) cout<<ans;else cout<<-1;}return 0;
}这篇关于蓝桥杯2023年第十四届省赛真题-买瓜|DFS+剪枝的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
